P4638 [SHOI2011] 银行家

你在一家银行工作，任务是帮助客户取出他们存放在保险箱里的金币。 银行里有 $m$ 个保险箱，你没有办法打开这些保险箱，因为钥匙都在客户的手里。一个客户可能有很多个保险箱的钥匙，一个保险箱的钥匙也可能被多个客户拥有。今天早上，经理已经告知，你需要按照顺序接待 $n$ 个客户（任何客户都不会同时到场），你也知道，第 $i$ 个客户会要求取走 $c_i$​​ 枚金币。每个客户来到银行的时候，会打开所有他能打开的保险箱，然后从中取走 $c_i$​​ 枚金币（任何金币都没有区别），如果这些保险箱里的金币数量不足 ，他会感到不高兴，在取走尽量多的金币之后，到你的经理那里去投诉你们银行的服务质量太差了。 你当然不希望“上帝”的投诉让你丢了工作，于是想到了个补救的办法：虽然每个客户走的时候都会把保险箱重新关上，但是你可以在他取金币的时候，偷偷地调整被打开的保险箱里的金币数量，譬如说把 $1$ 号保险里多余的 $5$ 枚放到 $2$ 号里，这样说不定下个客户来的时候，就能取到更多的金币了。 尽管有这样的方法，还是可能没法完成所有客户的要求。然而，你希望，尽量帮助客户取走更多的金币，这样才能消除他们的怒气，保住这份来之不易的工作和薪水。

无

无

### 数据范围 测试点编号 .|n$\le$ .|m$\le$ . -|-|- 1|30|100 2|40|50 3|100|400 4|100|400 5|100|400 6|200|500 7|300|500 8|400|1500 9|500|2000 10|600|2500