又到了一年一度的明明生日了，明明想要买 样东西，巧的是，这 样东西价格都是 元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 样东西，再买第 样，那么就可以只花 元，更巧的是， 竟然等于 。
现在明明想知道，他最少要花多少钱。
第一行两个整数，。
接下来 行，每行 个数，第 行第 个为 。
我们保证 并且 。
特别的，如果 ，那么表示这两样东西之间不会导致优惠。
注意 可能大于 。
一个整数，为最小要花的钱数。
1 1 0
1
3 3 0 2 4 2 0 2 4 2 0
7
样例解释 。
先买第 样东西，花费 元，接下来因为优惠，买 样都只要 元，共 元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 元买剩下那件，而选择用 元。）
数据规模
对于 的数据，。
2018.7.25新添数据一组
