Problem Description

It's Mingming's birthday again, and he wants to buy $B$ items, all priced at $A$ yuan each.

However, the shop owner mentions a recent promotion:

If you buy the $I$-th item and then the $J$-th item, you can get them for just $K_{I,J}$ yuan. Interestingly, $K_{I,J}$ is equal to $K_{J,I}$.

Mingming now wants to know the minimum amount of money he needs to spend.

Input Format

The first line contains two integers, $A$ and $B$.

The next $B$ lines, each containing $B$ numbers, represent the matrix $K$. The $I$-th row and $J$-th column contains $K_{I,J}$.

We guarantee that $K_{I,J} = K_{J,I}$ and $K_{I,I} = 0$.

Specifically, if $K_{I,J} = 0$, it means there is no discount between these two items.

Note that $K_{I,J}$ can be greater than $A$.

Output Format

A single integer representing the minimum amount of money needed.

Sample Input and Output

Sample Input #1

1 1
0

Sample Output #1

1

Sample Input #2

3 3
0 2 4
2 0 2
4 2 0

Sample Output #2

7

Notes

Explanation for Sample #2:

First, buy the $2$-nd item for $3$ yuan. Then, due to the discount, buy the $1$-st and $3$-rd items for $2$ yuan each, totaling $7$ yuan.

(When multiple discounts apply, Mingming, being smart, will not choose to spend $4$ yuan on the remaining item but will instead choose to spend $2$ yuan.)

Data Size

For $30\%$ of the data, $1 \le B \le 10$.

For $100\%$ of the data, $1 \le B \le 500, 0 \le A, K_{I,J} \le 1000$.

A new set of data was added on July 25, 2018.

见题面 Input 部分

见题面 Output 部分