880032 - 最大价值

通过次数

6

提交次数

8

Time Limit : 1 秒
Memory Limit : 128 MB

一名种菜的农民伯伯,需要在给定的时间内完成种菜,现有m种不同的蔬菜提供给农民伯伯选择,且每种蔬菜种植花费的时间不同,每种蔬菜成熟后售卖的价值也不同。 要求

  1. 在限定的总时间内进行蔬菜种植,并且种植蔬菜的种类不能超出限制的数量;
  2. 选择最优的种植方案使得蔬菜成熟后售卖的总价值最大(可选择不同的蔬菜种植)。

例如: 给定的总时间限制为55,种植蔬菜的种类限制为3; 3种蔬菜,种菜的花费时间及售卖价格分别为:第一种21和9,第二种20和2,第三种30和21。

最优的种植方案是选择种植第一种和第三种,两种蔬菜种植总时间30+21,未超过总时间限制55。所种植蔬菜为两种,也未超过种类限制的3种。最大总价值为9+21=30,这个方案是最优的。

Input

第一行输入两个正整数t(1≤t ≤ 600)和m(1 ≤ m ≤ 50),用一个空格隔开,t代表种菜总时间限制,m代表最多可种植蔬菜种类的限制 接下来的m行每行输入两个正整数t1(1 < t1< 101)和p(1 < p < 101)且用一个空格隔开,t1表示每种蔬菜种植需要花费的时间,p表示对应蔬菜成熟后售卖的价值。

Output

输出一个正整数,表示选择最优的种植方案后,蔬菜成熟后售卖的最大总价值

Examples

Input

55 3
21 9
20 2
30 21

Output

30

Hint

本题为01背包问题,属于模板题。