3055 - PRZ
时间限制 : 1 秒
内存限制 : 128 MB
一只队伍在爬山时碰到了雪崩，他们在逃跑时遇到了一座桥，他们要尽快的过桥。
桥已经很旧了, 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。 所以这只队伍过桥时只能分批过，当一组全部过去时，下一组才能接着过。队伍里每个人过桥都需要特定的时间，当一批队员过桥时时间应该算走得最慢的那一个，每个人也有特定的重量，我们想知道如何分批过桥能使总时间最少。
输入
第一行两个数: W 表示桥能承受的最大重量和 n 表示队员总数。
接下来 n 行：每行两个数: t 表示该队员过桥所需时间和 w 表示该队员的重量。
输出
输出一个数表示最少的过桥时间。
样例
输入
100 3 24 60 10 40 18 50
输出
42
提示
对于 100\% 的数据，100\le W \le400 ，1\le n\le 16，1\le t\le50，10\le w\le100
来源
其它比赛