← 返回题目列表

AtCoder · arc129_e

E. 又一个最小化

中文机器翻译题面 查看原题

分数: 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