买礼物

题目描述

又到了一年一度的明明生日了,明明想要买$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$,那么表示这两样东西之间不会导致优惠。

输出格式


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

输入输出样例

输入样例 #1

1 1
0

输出样例 #1

1

输入样例 #2

3 3
0 2 4
2 0 2
4 2 0

输出样例 #2

7

说明

样例解释$2$ 先买第$2$样东西,花费$3$元,接下来因为优惠,买$1,3$样都只要$2$元,共$7$元。 (同时满足多个“优惠”的时候,聪明的明明当然不会选择用$4$元买剩下那件,而选择用$2$元。) 数据规模 对于$30\%$的数据,$1 \le B \le 10$。 对于$100\%$的数据,$1 \le B \le 500,0 \le A,K_{I,J} \le 1000$。 2018.7.25新添数据一组