题目描述

学生在 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分。

现在要进行一次竞赛，总时间 T 固定，有若干类型可选的题目，每种类型题目可选入的数量不限，每种类型题目有一个 $s_i$ （解答此题所得的分数）和 $t_i$ （解答此题所需的时间）。

现需要选择若干题目，是的这些题的总时间 T 以内的前提下，所得的总分最大。

输入格式

第 1 行: 两个整数，竞赛的时间 t( 1<= t<=10000 )和题目种类数 n（1 <= n <= 100000 ) 。

第 2 ~ n+1 行: 第一个整数说明解决这种题目能得到的分数( 1 <= $s_i$ <= 100000)，第二个整数说明这种题目所需的时间（ 1<= $t_i$ <= 100000 )

输出格式

单独的一行，在给定的时间里得到的最大分数。

样例

300 4
100 60
250 120
120 100
35 20

605

样例解释

从第 2 类型中选两题和第 4 中类型中选三题。