题目描述

你是一名火星救援队的后勤主管。一艘无人货运飞船即将发射前往火星基地，飞船的货舱剩余载重能力有限。基地发来了一个急需物资清单，清单上有 $M$ 种不同的救援物资。每种物资都有固定的重量和对应的“生存价值”（代表该物资对宇航员生存的重要程度）。

由于飞船空间限制，你只能选择部分物资装入货舱，且每种物资只有一件（不可分割，要么全装，要么不装）。你的任务是在不超过飞船最大载重的前提下，使得装入物资的总生存价值最大。

输入格式

第一行包含两个整数 $W 和 M (1≤W≤1000,1≤M≤100)$，分 别表示飞船的最大载重能力和物资的种类数目。

接下来$M$行，每行包含两个整数 $w_i和v_i (1≤w_i ,v_i ≤100)$，分别表示第$i$种物资的重量和生存价值。

输出格式

输出一个整数，表示在不超过最大载重的情况下，能装入物资的最大总生存价值。

70 3
71 100
69 1
1 2

3

10 3
4 7
5 8
2 3

15

样例2解释：

最大载重为10。

如果选物资1（重4，值7）和物资2（重5，值8），总重9 <= 10，总价值15。

如果选物资1（重4，值7）和物资3（重2，值3），总重6 <= 10，总价值10。

如果选物资2（重5，值8）和物资3（重2，值3），总重7 <= 10，总价值11。

如果全选，总重11 > 10，不可行。