#P2031. 买礼物
买礼物
题目描述
又到了一年一度的明明生日了,明明想要买 B 样东西,巧的是,这 B 样东西价格都是 A 元。
但是,商店老板说最近有促销活动,也就是:
如果你买了第 I 样东西,再买第 J 样,那么就可以只花 K{I,J}元,更巧的是,K{I,J}竟然等于 K{J,I}
现在明明想知道,他最少要花多少钱。
1≤B≤500,0≤A,K{I,J} ≤1000
输入格式
第一行两个整数,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
0
1
3 3
0 2 4
2 0 2
4 2 0
7
Limitation
1s, 1024KiB for each test case.
样例说明
样例解释 2。
先买第 2 样东西,花费 3 元,接下来因为优惠,买 1,3 样都只要 2 元,共 7 元。
(同时满足多个“优惠”的时候,聪明的明明当然不会选择用 4 元买剩下那件,而选择用 2 元。)