201294: [AtCoder]ARC129 E - Yet Another Minimization

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