문제

어느 강에서 한쪽 강가에서 출발하여 돌 위를 차례차례 뛰어넘어 반대쪽 강가까지 가는 조금 위험한 게임이 유행하고 있다.

그림 $4\text{-}1$: 돌의 위치 예시 (그림의 일본어 표기: 反対側の岸 = 반대쪽 강가, 川 = 강, 始める岸 = 시작하는 강가, 列 = 열, 行 = 행)

이제 그림 $4\text{-}1$과 같이 돌이 격자 칸 위에 존재한다고 생각하자. 행의 개수는 $n$이다. 그림 $4\text{-}1$에서는 $n = 5$이다.

이 게임에서는 한쪽 강가에서 시작하여 일반 점프 또는 $m$회 이하의 한 행 건너뛰기 점프를 하여 반대쪽 강가까지 건넌다. 일반 점프란 현재 있는 행에서 바로 다음($1$행 앞) 행의 강가 또는 돌 중 하나로 뛰어 옮겨가는 것이며, 한 행 건너뛰기 점프란 현재 있는 행에서 두 칸 앞($2$행 앞) 행의 강가 또는 돌 중 하나로 뛰어 옮겨가는 것이다. 시작하는 강가의 $1$행 앞은 $1$번째 행, $2$행 앞은 $2$번째 행이며, $n-1$번째 행의 $2$행 앞과 $n$번째 행의 $1$행 앞은 반대쪽 강가라고 한다.

이제 이 게임을 가능한 한 안전하게 수행하기 위해 점프의 위험도라는 것을 생각하기로 했다. 각 돌에는 미끄러운 정도가 정해져 있다. 돌에서 돌로 뛰어 옮겨갈 때의 점프의 위험도는 일반 점프이든 한 행 건너뛰기 점프이든 상관없이 다음과 같이 정의한다.

(현재 있는 돌의 미끄러운 정도 $+$ 뛰어 옮겨갈 돌의 미끄러운 정도) $\times$ (가로 이동 거리)

단, 가로 이동 거리란 열 번호의 차이이다. 또한, 강가에서 돌로, 혹은 돌에서 강가로 뛰어 옮겨가는 점프의 위험도는 $0$으로 한다.

입력으로 $n, m$과 각 돌의 위치 및 미끄러운 정도가 주어졌을 때, 반대쪽 강가까지 도달할 때의 점프 위험도 합의 최솟값을 구하는 프로그램을 작성하라. 주어지는 입력 데이터는 반드시 반대쪽 강가까지 도달할 수 있도록 되어 있으며, 같은 칸에 돌이 $2$개 이상 존재하지 않는다.

입력

$1$번째 줄에는 공백으로 구분된 $2$개의 정수 $n, m$이 적혀 있다. 이는 행의 개수와 한 행 건너뛰기 점프의 허용 횟수를 나타낸다. $n, m$은 각각 $2 \le n \le 150$, $0 \le m \le \frac{(n+1)}{2}$을 만족한다.

이어지는 $n$개의 줄에는 각 행에 있는 돌의 정보가 적혀 있다. $i+1$번째 줄($1 \le i \le n$)에는 $1$개의 정수 $k_{i}$($0 \le k_{i} \le 10$)와 그에 이어 $2 \times k_{i}$개의 정수가 공백으로 구분되어 적혀 있다. 이들은 시작하는 강가에서부터 세어 $i$번째 행에 있는 돌의 정보를 나타낸다.

$k_{i}$는 그 행에 존재하는 돌의 개수를 나타내며, 이어지는 $2 \times k_{i}$개의 정수 중 $2 \times j - 1$번째($1 \le j \le k_{i}$) 정수 $x_{i,j}$는 그 행의 $j$번째 돌의 열 번호를, $2 \times j$번째 정수 $d_{i,j}$는 그 행의 $j$번째 돌의 미끄러운 정도를 각각 나타낸다. $x_{i,j}, d_{i,j}$는 각각 $1 \le x_{i,j}, d_{i,j} \le 1000$을 만족한다.

채점용 데이터 중 배점의 $20\%$에 해당하는 데이터는 $n \le 6$을 만족하며, 배점의 다른 $20\%$에 해당하는 데이터는 $m = 0$을 만족한다.

출력

출력은 반대쪽 강가까지 도달할 때의 점프 위험도 합의 최솟값을 나타내는 $1$개의 정수를 포함한 $1$줄로 이루어진다.

예시

그림 $4\text{-}2$에서 돌에 적힌 숫자는 각 돌의 미끄러운 정도를 나타낸다고 하자. 화살표로 표시된 순서대로 돌을 건널 때, 각 점프의 위험도는 순서대로 $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$이며, 합계는 $17$이 된다. 이때 점프 위험도의 합계가 최소가 된다.

이 예시는 입출력 예시 $1$에 대응한다.

그림 $4\text{-}2$: 경로의 예시

입출력 예시

위의 예시에 대응하는 입출력은 예시 $1$과 같다.

입력 예시 1

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

출력 예시 1

17

입력 예시 2

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

출력 예시 2

40