题目描述

小华要买 $B$ 样东西，每样东西的原价都是 $A$ 元。

商家推出了促销活动：如果你先买了第 $I$ 样东西，再买第 $J$ 样，那么第 $J$ 样只需要 $K_{I,J}$ 元。注意 $K_{I,J}=K_{J,I}$。

小华想知道，他最少要花多少钱买下全部 $B$ 样东西。

输入格式

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

输出格式

一个整数，表示最少花费。

样例

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

提示

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

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