问题描述

Snuke正在生成一个长度为$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