题目描述

すぬけくんは，長さ $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}$ のコストが追加でかかります．

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

输入格式

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

$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}$

输出格式

答えを出力せよ．

题目大意

Snuke 正在构造一个长度为 $n$ 的整数序列 $x = (x_1,x_2,\cdots,x_n)$。对于每个 $1\le i \le n$，$x_i$ 都有 $m$ 个候选值，其中第 $k$ 个记作 $a_{i,k}$。选择 $a_{i,k}$ 需要花费 $c_{i,k}$。

此外，在确定序列 $x$ 后，对每对满足 $1\le i < j \le n$ 的 $(i,j)$ 还需要花费 $|x_i-x_j|\times W_{i,j}$。

请输出最小花费。

$2\le n\le 50,\ 2\le m \le 5,\ 1\le a_{i,1} < a_{i,2} < \cdots < a_{i,m} \le 10^6,\ 1\le c_{i,k} \le 10^{15},\ 1\le W_{i,j}\le 10^6$ 。

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

28

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

提示

制約

• $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$
• 入力される値はすべて整数である

Sample Explanation 1

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