Условие задачи

На одной реке популярна довольно опасная игра: нужно перебраться с одного берега на противоположный, прыгая с камня на камень.

Рисунок $4\text{-}1$: Пример расположения камней (Японские надписи на рисунке: 反対側の岸 = Противоположный берег, 川 = Река, 始める岸 = Начальный берег, 列 = Столбец, 行 = Строка)

Как показано на Рисунке $4\text{-}1$, будем считать, что камни располагаются в клетках сетки. Количество строк равно $n$. На Рисунке $4\text{-}1$ значение $n = 5$.

В этой игре, начиная с одного берега, вы переправляетесь на противоположный берег, совершая обычные прыжки или не более $m$ прыжков через строку. Обычный прыжок — это прыжок на берег или на один из камней в строке, находящейся на $1$ строку впереди текущей, а прыжок через строку — это прыжок на берег или на один из камней в строке, находящейся на $2$ строки впереди текущей. Здесь строкой на $1$ строку впереди начального берега является строка $1$, строкой на $2$ строки впереди — строка $2$, а строкой на $2$ строки впереди строки $n-1$, равно как и строкой на $1$ строку впереди строки $n$, является противоположный берег.

Чтобы пройти эту игру как можно безопаснее, было решено учитывать опасность прыжка. У каждого камня есть фиксированная скользкость. При прыжке с одного камня на другой, будь то обычный прыжок или прыжок через строку, опасность прыжка определяется как:

(скользкость текущего камня $+$ скользкость целевого камня) $\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