P1194 买礼物

又到了一年一度的明明生日了，明明想要买 $B$ 样东西，巧的是，这 $B$ 样东西价格都是 $A$ 元。 但是，商店老板说最近有促销活动，也就是： 如果你买了第 $I$ 样东西，再买第 $J$ 样，那么就可以只花 $K_{I,J}$ 元，更巧的是，$K_{I,J}$ 竟然等于 $K_{J,I}$。 现在明明想知道，他最少要花多少钱。

无

无

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