Background

又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 I 样东西，再买第 J 样，那么就可以只花 K ~I,J~ 元，更巧的是，K~I,J~竟然等于 K ~J,I~。

现在明明想知道，他最少要花多少钱。

Format

Input

第一行两个整数，A,B。

接下来 B 行，每行 B 个数，第 I 行第 J 个为 K ~I,J~。

我们保证 K ~I,J~=K ~J,I~并且 K ~I,I~=0。 特别的，如果 K ~I,J~=0，那么表示这两样东西之间不会导致优惠。注意 K ~I,J~可能大于 A。

Output

一个整数，为最小要花的钱数。

Samples

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

Limitation

样例解释 2。 先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。 （同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）

数据规模 对于 30% 的数据，1≤B≤10。 对于 100% 的数据，1≤B≤500,0≤A,K ~I,J~≤1000。