#P1194. 买礼物

买礼物

题目描述

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

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

如果你买了第 II 样东西,再买第 JJ 样,那么就可以只花 KI,JK_{I,J} 元,更巧的是,KI,JK_{I,J} 竟然等于 KJ,IK_{J,I}

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

输入格式

第一行两个整数,A,BA,B

接下来 BB 行,每行 BB 个数,第 II 行第 JJ 个为 KI,JK_{I,J}

我们保证 KI,J=KJ,IK_{I,J}=K_{J,I} 并且 KI,I=0K_{I,I}=0

特别的,如果 KI,J=0K_{I,J}=0,那么表示这两样东西之间不会导致优惠。

输出格式

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

1 1
0


1
3 3
0 2 4
2 0 2
4 2 0

7

提示

样例解释 22

先买第 22 样东西,花费 33 元,接下来因为优惠,买 1,31,3 样都只要 22 元,共 77 元。

(同时满足多个“优惠”的时候,聪明的明明当然不会选择用 44 元买剩下那件,而选择用 22 元。)

数据规模

对于 30%30\% 的数据,1B101\le B\le 10

对于 100%100\% 的数据,1B500,0A,KI,J10001\le B\le500,0\le A,K_{I,J}\le1000

2018.7.25新添数据一组