题目描述

我们把USACO竞赛的试题分为若干类，每类都有 $2$ 道题目。同一类题目分值相同，耗时也相同。你的任务是编写一个程序决定选择那些题目，使得考生在给定的时间内能得到尽可能多的分数。

输入格式

第一行包括两个整数 $M,N$。$M$ 代表竞赛的时间，$N$ 代表问题种类的数目。

第 $2\sim N+1$ 行每行包括两个整数--每类题目的分值和耗时。

输出格式

最大可能得到的分数。

100 2
200 51
50 49

250