Problem Statement

At a certain river, a slightly dangerous game of jumping from stone to stone from one bank to reach the opposite bank is popular.

Figure $4\text{-}1$: Example of stone positions (Japanese labels in the figure: 反対側の岸 = Opposite bank, 川 = River, 始める岸 = Starting bank, 列 = Column, 行 = Row)

Now, as shown in Figure $4\text{-}1$, we consider the stones to exist on a grid of squares. The number of rows is $n$. In Figure $4\text{-}1$, $n = 5$.

In this game, starting from one bank, you cross to the opposite bank by making normal jumps or at most $m$ single-row-skipping jumps. A normal jump is jumping to the bank or one of the stones in the row $1$ row ahead of the current row, and a single-row-skipping jump is jumping to the bank or one of the stones in the row $2$ rows ahead of the current row. Here, the row $1$ row ahead of the starting bank is row $1$, the row $2$ rows ahead is row $2$, and the row $2$ rows ahead of row $n-1$ as well as the row $1$ row ahead of row $n$ are the opposite bank.

Now, in order to accomplish this game as safely as possible, we decided to consider the danger level of a jump. Each stone has a fixed slipperiness. When jumping from one stone to another stone, whether it is a normal jump or a single-row-skipping jump, the danger level of the jump is defined as:

(slipperiness of the current stone $+$ slipperiness of the destination stone) $\times$ (horizontal movement distance)

Here, the horizontal movement distance is the difference between the column numbers. Also, the danger level of a jump from a bank to a stone, or from a stone to a bank, is $0$.

Given $n, m$ and the position and slipperiness of each stone as input, write a program to find the minimum possible total danger level of jumps when reaching the opposite bank. For the given input data, it is guaranteed that it is always possible to reach the opposite bank, and no square contains $2$ or more stones.

Input

On the $1$-st line, $2$ integers $n, m$ are written separated by a space. These represent the number of rows and the allowed number of single-row-skipping jumps. $n, m$ satisfy $2 \le n \le 150$ and $0 \le m \le \frac{(n+1)}{2}$, respectively.

On the following $n$ lines, information about the stones in each row is written. On the $i+1$-th line ($1 \le i \le n$), $1$ integer $k_{i}$ ($0 \le k_{i} \le 10$) followed by $2 \times k_{i}$ integers are written separated by spaces. These represent the information about the stones in the $i$-th row counting from the starting bank.

$k_{i}$ represents the number of stones existing in that row, and for the following $2 \times k_{i}$ integers, the $2 \times j - 1$-th ($1 \le j \le k_{i}$) integer $x_{i,j}$ represents the column number of the $j$-th stone in that row, and the $2 \times j$-th integer $d_{i,j}$ represents the slipperiness of the $j$-th stone in that row, respectively. $x_{i,j}, d_{i,j}$ satisfy $1 \le x_{i,j}, d_{i,j} \le 1000$, respectively.

Of the test data, $20\%$ of the score satisfies $n \le 6$, and another $20\%$ of the score satisfies $m = 0$.

Output

The output consists of $1$ line containing $1$ integer representing the minimum total danger level of jumps when reaching the opposite bank.

Example

In Figure $4\text{-}2$, suppose the numbers written on the stones represent the slipperiness of each stone. When crossing the stones in the order indicated by the arrows, the danger levels of the respective jumps are, in order, $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, and the total is $17$. In this case, the total danger level of the jumps is minimized.

This example corresponds to Sample $1$.

Figure $4\text{-}2$: Example of a route

Sample Input and Output

The input and output corresponding to the example above are as shown in Sample $1$.

Sample Input 1

5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

Sample Output 1

17

Sample Input 2

5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

Sample Output 2

40