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.

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.

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.

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

见题面 Input 部分

见题面 Output 部分