题目描述

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

要求:

1.在限定的总时间内进行蔬菜种植，并且种植蔬菜的种类不能超出限制的数量

2.选择最优的种植方案使得蔬菜成熟后售卖的总价值最大(可选择不同的蔬菜种植)

例如:

给定的总时间限制为$55$，种植蔬菜的种类限制为$3$

$3$种蔬菜种菜的花费时间及售卖价格分别为: 第一种 $21$和9，第二种$20$和$2$，第三种 $30$ 和$21$

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

输入

第一行输入两个正整数$t$和 $m$，用一个空格隔开，$t$代表种菜总时间限制，m代表最多可种植蔬菜种类的限制

接下来的 $m$ 行每行输入两个正整数$t_i$和$p_i$且用一个空格隔开，$t_i$表示每种蔬菜种植需要花费的时间，$p_i$表示对应蔬菜成熟后售卖的价值

输出

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

55 3
21 9
20 2
30 21

30

100 1
9 42

462

提示

$1<=t<=600$

$1<=m<=50$

$1<ti<101$

$1<pi<101$