问题说明

阿里巴巴发现了一个海盗藏宝的山洞，在这个山洞中有一些宝箱，每一个宝箱有它自身的价值以及重量，阿里巴巴有一只毛驴，这只毛驴的载重量为T，阿里巴巴需要通过这只毛驴来搬运这些宝箱，但是由于时间问题，他只能搬运一次，那么如果你是阿里巴巴，在不超出毛驴载重量的情况下，如何选择宝箱能达到一次运输的最大价值，请输出最大价值是多少。

输入格式

第一行2个整数，代表毛驴的载重量T(1<=T<=1000)，以及宝箱的数量m(1<=m<=100)；

接下来m行，每行两个1到100之间的整数，代表每个宝箱的重量w以及价值v.

输出格式

输出最大价值。

70 3
71 100
69 1
1 2

3

来源/分类