問題文

すぬけくんは，長さ $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}$

出力

答えを出力せよ．

入力例 1

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

出力例 1

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$ のコストがかかる．

入力例 2

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

出力例 2

27790

入力例 3

2 2
1 1
10 10
1 1
10 10
100

出力例 3

2