题目描述

すぬけ君想要构造一个长度为 $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}$ $\cdots$ $A_{1,M}$ $C_{1,M}$ $A_{2,1}$ $C_{2,1}$ $A_{2,2}$ $C_{2,2}$ $\cdots$ $A_{2,M}$ $C_{2,M}$ $\cdots$ $A_{N,1}$ $C_{N,1}$ $A_{N,2}$ $C_{N,2}$ $\cdots$ $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}$ $\cdots$ $W_{N-1,N}$

输出格式

请输出答案。

样例 1

输入

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

输出

28

样例 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

输出

27790

样例 3

输入

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$
• 所有输入的值均为整数

样例解释 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$。

由 ChatGPT 4.1 翻译