Умова задачі

На одній річці популярна дещо небезпечна гра: потрібно перебратися з одного берега на протилежний, стрибаючи з каменя на камінь.

Рисунок $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