/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
すぬけくんは，長さ 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
Score : 900 points
Problem Statement
Snuke is making an integer sequence of length N: x=(x_1,x_2,\cdots,x_N). For each i (1 \leq i \leq N), there are M candidates for the value of x_i: the k-th of them is A_{i,k}. Choosing A_{i,k} incurs a cost of C_{i,k}.
Additionally, after deciding x, a cost of |x_i-x_j| \times W_{i,j} is incurred for each i,j (1 \leq i < j \leq N).
Find the minimum possible total cost incurred.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
3 2 1 1 5 2 2 3 9 4 7 2 8 2 1 5 3
Sample Output 1
28
An optimal choice is x=(5,9,7). The individual costs incurred here are as follows.
- Choosing A_{1,2} for x_1 incurs a cost of C_{1,2}=2.
- Choosing A_{2,2} for x_2 incurs a cost of C_{2,2}=4.
- Choosing A_{3,1} for x_3 incurs a cost of C_{3,1}=2.．
- For (i,j)=(1,2), a cost of |x_i-x_j| \times W_{i,j}=4 is incurred.
- For (i,j)=(1,3), a cost of |x_i-x_j| \times W_{i,j}=10 is incurred.
- For (i,j)=(2,3), a cost of |x_i-x_j| \times W_{i,j}=6 is incurred.
Sample Input 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
Sample Output 2
27790
Sample Input 3
2 2 1 1 10 10 1 1 10 10 100
Sample Output 3
2