Description

It is Mingming’s birthday again. Mingming wants to buy $B$ kinds of items, and coincidentally, each of these $B$ items is priced at $A$ yuan.

However, the shop owner says there is a promotion:

If you have bought item $I$, then when you buy item $J$, you only need to pay $K_{I,J}$ yuan. Moreover, $K_{I,J}$ happens to equal $K_{J,I}$.

Now Mingming wants to know the minimum amount of money he has to spend.

Input Format

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

Then there are $B$ lines, each containing $B$ numbers. The $I$-th line and $J$-th number is $K_{I,J}$.

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

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

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

Output Format

Output a single integer, the minimum total amount of money required.

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

Hint

Explanation for Sample $2$.

Buy item $2$ first, spending 3 yuan. Then, due to the promotion, buying items $1$ and $3$ each costs 2 yuan, for a total of 7 yuan.

(When multiple “discounts” apply at the same time, clever Mingming will of course not choose to pay 4 yuan for the remaining one, but choose to pay 2 yuan.)

Constraints

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

For $100\%$ of the testdata, $1\le B\le500,0\le A,K_{I,J}\le1000$.

Added one more set of testdata on 2018.7.25.

Translated by ChatGPT 5