问题描述

详见教材p251问题描述： 学生在 USACO竞赛中得分越多我们越高兴。我们试着设计竞赛以便学生尽可能多得分。现在要进行一次竞赛，总时间 T 固定，有若干类型可选的题目，每种类型题目可选入的数量不限，每种类型题目有一个 s (解答此题所得的分数)和 ti (解答此题所需的时间)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大。

格式

输入

第 1 行：两个整数，竞赛的时间 t (1≤t≤10000) 和题目类型数 n (1≤n≤10000)； 第 2~n+1 行：两个整数，每种类型题目的分数和耗时。第一个整数说明解决这种题目能得的分数(1≤si≤10000)，第二个整数说明解决这种题目所需的时间(1≤ti<10000)。

输出

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

样例说明：从第2种类型中选两题和第4种类型中选三题。

样例

300 4
100 60
250 120
120 100 
35 20

605

限制

1s, 64MB.