分数: 900 点
问题陈述
Snuke 正在制作一个长度为整数的序列 N: x=(x_1,x_2,\cdots,x_N)。 对于每个 i (1 \leq i \leq N),有 M 候选人的价值 x_i: k- 其中第一个是 A_{i,k}。 选择 A_{i,k} 产生的费用为 C_{i,k}.
另外,在决定之后 x,成本为 每个都会产生 |x_i-x_j| \times W_{i,j} 为每个产生 i,j (1 \leq i < j \leq N).
找出可能产生的最小总成本。
约束
- 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)。 这里产生的个人费用如下。
- 选择 产生了 A_{1,2} 为 x_1 产生的费用为 C_{1,2}=2.
- 选择 产生了 A_{2,2} 为 x_2 产生的费用为 C_{2,2}=4.
- 选择 产生了 A_{3,1} 为 x_3 产生的费用为 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