题目描述

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

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

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

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

输入格式

第一行两个整数，$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$。

输出格式

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

数据范围与约定

对于 $30\%$ 的数据，$1\le B\le 10$。

对于 $100\%$ 的数据，$1\le B\le500,0\le A,K_{I,J}\le1000$。

2018.7.25新添数据一组

可见测试数据

输入数据 1

1 1
0

输出数据 1

1

输入数据 2

3 3
0 2 4
2 0 2
4 2 0

输出数据 2

7

输入数据 3

5 3
0 1 0
1 0 2
0 2 0

输出数据 3

8