【问题描述】
现在有个神奇的网络游戏，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。