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.