Coding is the closest thing we have to a surperpower
描述
又到了一年一度的明明生日了，明明想要买 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}=0，那么表示这两样东西之间不会导致优惠。
数据保证：k_{i,j}=k_{j,i},\ k_{i,i}=0,\ 1 \leq B \leq 500,\ 0 \leq A,k_{i,j} \leq 1000
输出
一个整数，为最少要花的钱数。
样例
输入
1 1 0
输出
1
输入
3 3 0 2 4 2 0 2 4 2 0
输出
7
提示
【样例解释 2】
先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。
（同时满足多个优惠的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）
标签