깡충깡충 강 건너기

어떤 강에서, 한쪽 기슭에서 시작해 돌 위를 차례로 뛰어 옮기며 반대쪽 기슭까지 가는 다소 위험한 놀이가 유행하고 있다.

그림 4-1. 돌 위치의 예

그림 4-1처럼 돌은 격자 칸 위에 놓여 있다고 하자. 행의 수는 $n$이며, 그림 4-1에서는 $n = 5$이다.

이 놀이에서는 한쪽 기슭에서 출발해 보통 점프 또는 한 행 건너뛰기 점프를 최대 $m$번까지 사용하여 반대쪽 기슭까지 건넌다. 보통 점프는 지금 있는 행보다 한 행 앞의 기슭 또는 돌 중 하나로 뛰어 옮기는 것이고, 한 행 건너뛰기 점프는 지금 있는 행보다 두 행 앞의 기슭 또는 돌 중 하나로 뛰어 옮기는 것이다. 출발 기슭의 한 행 앞은 1번째 행, 두 행 앞은 2번째 행이며, $n-1$번째 행의 두 행 앞과 $n$번째 행의 한 행 앞은 반대쪽 기슭이라고 한다.

이 놀이를 되도록 안전하게 마치기 위해 점프의 위험도를 생각한다. 각 돌에는 미끄러움 값이 정해져 있다. 돌에서 돌로 뛰어 옮길 때의 위험도는 보통 점프든 한 행 건너뛰기 점프든

$$(\text{현재 돌의 미끄러움} + \text{도착 돌의 미끄러움}) \times (\text{가로 이동 거리})$$

로 정한다. 여기서 가로 이동 거리는 두 돌의 열 번호 차이다. 또한 기슭에서 돌로, 또는 돌에서 기슭으로 뛰어 옮기는 점프의 위험도는 $0$이다.

$n$, $m$과 각 돌의 위치 및 미끄러움이 입력으로 주어질 때, 반대쪽 기슭까지 도달하는 데 드는 점프 위험도 합의 최솟값을 구하는 프로그램을 작성하라. 주어지는 입력 데이터는 반드시 반대쪽 기슭까지 도달할 수 있으며, 같은 칸에 돌이 2개 이상 놓이는 일은 없다.

첫째 줄에 두 정수 $n$, $m$이 공백으로 구분되어 주어진다. 각각 행의 수와 한 행 건너뛰기 점프가 허용되는 횟수를 나타낸다. $2 \le n \le 150$, $0 \le m \le (n+1)/2$이다.

이어지는 $n$개의 줄에는 각 행의 돌 정보가 주어진다. $i+1$번째 줄 $(1 \le i \le n)$에는 정수 $k_i$ $(0 \le k_i \le 10)$가 먼저 오고, 그 뒤에 $2 k_i$개의 정수가 공백으로 구분되어 온다. 이는 출발 기슭에서 세어 $i$번째 행에 있는 돌 정보를 나타낸다. $k_i$는 그 행에 있는 돌의 개수이며, 이어지는 $2 k_i$개의 정수 가운데 $2j-1$번째 정수 $x_{i,j}$ $(1 \le j \le k_i)$는 그 행 $j$번째 돌의 열 번호를, $2j$번째 정수 $d_{i,j}$는 그 돌의 미끄러움을 나타낸다. $x_{i,j}$, $d_{i,j}$는 $1 \le x_{i,j}, d_{i,j} \le 1000$을 만족한다.

반대쪽 기슭까지 도달하는 데 드는 점프 위험도 합의 최솟값을 나타내는 정수 하나를 한 줄에 출력한다.

그림 4-2. 경로의 예

그림 4-2에서 돌에 적힌 숫자는 각 돌의 미끄러움을 나타낸다. 화살표로 표시된 순서대로 돌을 건널 때 각 점프의 위험도는 차례로 $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$이며 그 합은 $17$이다. 이때 점프 위험도의 합이 최소가 된다. 이 경로는 첫 번째 입력 데이터에 대응한다.