Hop-Hop River Crossing

On a certain river, a somewhat dangerous game is popular: starting from one bank, you hop from stone to stone until you reach the opposite bank.

Figure 4-1. Example of stone positions

As in Figure 4-1, assume the stones sit on the cells of a grid. The number of rows is $n$; in Figure 4-1, $n = 5$.

In this game you start from one bank and cross to the opposite bank using normal jumps and at most $m$ row-skipping jumps. A normal jump moves you onto the bank or one of the stones in the row one ahead of your current row; a row-skipping jump moves you onto the bank or one of the stones in the row two ahead of your current row. The row one ahead of the starting bank is row 1 and the row two ahead is row 2; the row two ahead of row $n-1$ and the row one ahead of row $n$ are both the opposite bank.

To finish this game as safely as possible, we consider the danger of a jump. Each stone has a fixed slipperiness. The danger of hopping from one stone to another, whether by a normal jump or a row-skipping jump, is defined as

$$(\text{slipperiness of the current stone} + \text{slipperiness of the destination stone}) \times (\text{horizontal distance moved})$$

where the horizontal distance is the difference between the two stones' column numbers. A jump from the bank onto a stone, or from a stone onto the bank, has danger $0$.

Given $n$, $m$, and the position and slipperiness of every stone, write a program that finds the minimum possible total danger of the jumps used to reach the opposite bank. The input is guaranteed to allow reaching the opposite bank, and no cell holds two or more stones.

The first line contains two integers $n$ and $m$ separated by a space: the number of rows and the number of row-skipping jumps allowed. They satisfy $2 \le n \le 150$ and $0 \le m \le (n+1)/2$.

Each of the next $n$ lines describes the stones in one row. Line $i+1$ $(1 \le i \le n)$ starts with an integer $k_i$ $(0 \le k_i \le 10)$ followed by $2 k_i$ space-separated integers, describing the stones in the $i$-th row counting from the starting bank. $k_i$ is the number of stones in that row. Among the following $2 k_i$ integers, the $(2j-1)$-th integer $x_{i,j}$ $(1 \le j \le k_i)$ is the column number of the $j$-th stone in that row, and the $2j$-th integer $d_{i,j}$ is that stone's slipperiness. They satisfy $1 \le x_{i,j}, d_{i,j} \le 1000$.

Print a single line containing one integer: the minimum total danger of the jumps needed to reach the opposite bank.

Figure 4-2. Example of a path

In Figure 4-2 the number written on each stone is its slipperiness. Crossing the stones in the order shown by the arrows, the danger of each jump is, in order, $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, for a total of $17$, which is the minimum possible total danger. This path corresponds to the first input case.