时间限制：1 S

内存限制：64 MB

【题目描述】

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

要求：

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

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

【输入格式】

第一行输入两个正整数 \(t\) (\(1 \le t \le 600\)) 和 \(m\) (\(1 \le m \le 50\)) ，用一个空格隔开，\(t\) 代表种菜总时间限制，\(m\) 代表最多可种植蔬菜种类的限制。

接下来 \(m\) 行，每行输入两个正整数 \(t_1\) (\(1 \lt t_1 \lt 101\)) 和 \(p\) (\(1 \lt p \lt 101\)) 且用一个空格隔开，\(t_1\) 表示每种蔬菜种植需要花费的时间，\(p\) 表示对应蔬菜成熟后售卖的价值。

【输出格式】

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

样例 1

【样例 1 输入】

55 3
21 9
20 2
30 21

【样例 1 输出】

30

【样例 1 解释】

给定的总时间限制为 \(55\) ，种植蔬菜的种类限制为 \(3\) ；

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

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