题目描述

在召唤师峡谷中，有很多英雄，但只有在真正战斗中独当一面的，才配得上“英雄”这个称号。有的英雄总是依赖召唤师的保护，一旦脱离温室，便无所作为。 现在，你作为一名召唤师，需要带领最多的英雄出战，但你的召唤空间有限（背包容量有限）。每个英雄都有“所需能量值”（体积）和“战斗力”（价值）。你只能挑选部分英雄，使得他们所需能量之和不超过你的召唤空间，同时总战斗力最大。

输入格式

第一行输入两个整数 m 和 n，分别代表召唤师空间容量m（1≤m≤200）和英雄数量n（1≤n≤30）。 接下来n行，每行输入两个整数，分别为第i个英雄所需能量值 w 和战斗力 v（1≤w,v≤200）。

输出格式

输出你能带领出战的最大总战斗力。

样例

10 3
2 5
4 11
6 13

24