Есептің шарты

Бір өзенде бір жағадан екінші қарама-қарсы жағаға тастан-тасқа секіріп өту сияқты аздап қауіпті ойын сәнге айналған.

$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