配点 : $900$ 点

問題文

すぬけくんは，長さ $N$ の整数列 $x=(x_1,x_2,\cdots,x_N)$ を作ろうとしています． 各 $i$ ($1 \leq i \leq N$) について，$x_i$ の値の候補が $M$ 種類あり，そのうち $k$ 種類目の値は $A_{i,k}$ です． なお，$A_{i,k}$ を選ぶ場合には，$C_{i,k}$ のコストがかかります．

また，$x$ を決めたあと，各 $i,j$ ($1 \leq i < j \leq N$) について， $|x_i-x_j| \times W_{i,j}$ のコストが追加でかかります．

最終的なコストの総和としてありうる最小値を求めてください．

制約

• $2 \leq N \leq 50$
• $2 \leq M \leq 5$
• $1 \leq A_{i,1} < A_{i,2} < \cdots < A_{i,M} \leq 10^6$
• $1 \leq C_{i,k} \leq 10^{15}$
• $1 \leq W_{i,j} \leq 10^6$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

$A_{1,1}$ $C_{1,1}$

$A_{1,2}$ $C_{1,2}$

$\vdots$

$A_{1,M}$ $C_{1,M}$

$A_{2,1}$ $C_{2,1}$

$A_{2,2}$ $C_{2,2}$

$\vdots$

$A_{2,M}$ $C_{2,M}$

$\vdots$

$A_{N,1}$ $C_{N,1}$

$A_{N,2}$ $C_{N,2}$

$\vdots$

$A_{N,M}$ $C_{N,M}$

$W_{1,2}$ $W_{1,3}$ $\cdots$ $W_{1,N-1}$ $W_{1,N}$

$W_{2,3}$ $W_{2,4}$ $\cdots$ $W_{2,N}$

$\vdots$

$W_{N-1,N}$

出力

答えを出力せよ．

3 2
1 1
5 2
2 3
9 4
7 2
8 2
1 5
3

28

$x=(5,9,7)$ とすればよいです． このときかかるコストの内訳は以下のとおりです．

• $x_1$ として $A_{1,2}$ を選んだので，$C_{1,2}=2$ のコストがかかる．
• $x_2$ として $A_{2,2}$ を選んだので，$C_{2,2}=4$ のコストがかかる．
• $x_3$ として $A_{3,1}$ を選んだので，$C_{3,1}=2$ のコストがかかる．
• $(i,j)=(1,2)$ について，$|x_i-x_j| \times W_{i,j}=4$ のコストがかかる．
• $(i,j)=(1,3)$ について，$|x_i-x_j| \times W_{i,j}=10$ のコストがかかる．
• $(i,j)=(2,3)$ について，$|x_i-x_j| \times W_{i,j}=6$ のコストがかかる．

10 3
19 2517
38 785
43 3611
3 681
20 758
45 4745
6 913
7 2212
22 536
4 685
27 148
36 2283
25 3304
36 1855
43 2747
11 1976
32 4973
43 3964
3 4242
16 4750
50 24
4 4231
22 1526
31 2152
15 2888
28 2249
49 2208
31 3127
40 3221
47 4671
24 6 16 47 42 50 35 43 47
29 18 28 24 27 25 33 12
5 43 20 9 39 46 30
40 24 34 5 30 21
50 6 21 36 5
50 16 13 13
2 40 15
25 48
20

27790

2 2
1 1
10 10
1 1
10 10
100

2