3711: 过河
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
现在有个神奇的网络游戏，A_love手下有n个士兵，前方有一条河，河上有一座桥，现在A_love已经度过河了，他要安排自己的士兵渡河，已知桥有最大载重量K，每个士兵有重量W_i,过桥时间T_i，桥上同一时刻最多有一队士兵，这队士兵的重量显然不能超过桥的最大载重量，为了体现互帮互助的良好精神，一队士兵渡河的时间应为这队士兵中的最大渡河时间，现在A_love需要安排士兵过河，求问过河的最少时间
输入
第一行是K，n。
K是桥的最大载重量，n是士兵个数。
以下n行，每行两个数，依次表示T_i,W_i。
输出
输出最少时间。
样例输入 复制
100 3
24 60
10 40
18 50
样例输出 复制
42
提示
对于30%的数据：n <= 11。
对于100%的数据：100<=K<=400,1<=n<=16,1<=T_i<=50,10<=W_i<=100。