Problem Name: Jumping Rivers
Problem
Problem Description: In a certain river, a slightly dangerous game is popular where you jump from one stone to another on the riverbank and go to the opposite bank.
Consider that the stones are located on the squares as shown in Figure 4-1. The number of rows is n. n = 5 in Figure 4-1.
In this game, starting from one bank, you can jump to the opposite bank by making a normal jump or a one-line jump that allows up to m jumps. A normal jump is jumping to the bank or stone one row ahead of the current row. A one-line jump is jumping to the bank or stone on the second row ahead of the current row. The row one ahead of the starting bank is the first row, and the row two ahead of it is the second row. Assume that the second row ahead of the row n-1 and the row one ahead of the row n are on the opposite bank.
Now, to safely complete this game, we decided to consider something called the danger level of a jump. Each stone has a determined slipperiness. The danger level of a jump when jumping from one stone to another is determined by multiplying the slipperiness of the stone you are on and the stone you are jumping to by the lateral distance, regardless of whether it is a normal jump or a one-line jump. Here, the lateral distance is the difference in column numbers. Also, the danger level of a jump from the bank to the stone or from the stone to the bank is 0.
Given n, m, the position and slipperiness of each stone, find the minimum total danger level of jumps to reach the opposite bank. The input data given always allows you to reach the opposite bank, and there are no more than two stones in the same square.
Input
The input consists of multiple datasets. Each dataset is given in the following format.
The first line of the input contains two integers n and m separated by a space. These represent the number of rows and the number of jumps allowed for one-line jumps, respectively. n and m satisfy 2 ≤ n ≤ 150 and 0 ≤ m ≤ (n+1)/2.
Each of the following n lines describes the stones on each row. For the i-th row (1 ≤ i ≤ n), a single integer k
i
(0 ≤ k
i
≤ 10) is followed by 2 × k
i
integers separated by spaces. These represent the information on the stones on the i-th row as seen from the starting bank.
Here, k
i
represents the number of stones in that row, and the 2 × k
i
integers that follow represent the column number x
i,j
and the slipperiness d
i,j
of the j-th stone in that row. The integers x
i,j
and d
i,j
satisfy 1 ≤ x
i,j
, d
i,j
≤ 1000.
For 20% of the total score, n ≤ 6 holds for each input dataset. For another 20% of the total score, m = 0 holds.
The input ends when n and m are both 0. The number of datasets is no more than 10.
Output
For each dataset, output one line containing an integer representing the minimum total danger level of jumps to reach the opposite bank.
Example
Assume that the numbers written on the stones in Figure 4-2 represent the slipperiness of each stone. When crossing the stones in the order indicated by the arrows, the danger levels of the jumps are 0, (2 + 2) × 1 = 4, (2 + 1) × 1 = 3, (1 + 4) × 2 = 10, and 0, respectively, and the sum is 17. In this case, the total danger level is minimized. This example corresponds to the first input/output example.
Input/Output Examples
Input Example
5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
0 0
Output Example
17
40
The problem statement and the test data used in the automatic judging system are taken from the
Information Olympiad Japan Committee
.