小Y老师的骗钱法
小Y老师的骗钱法
题目描述
小Y老师是个赚钱不择手段的老师，他给比赛出题赚钱，然后参加那场比赛，这样就能骗到比赛的AK奖，领两次主办方的钱
同时小Y老师又很忙，所以他会去许多奇奇怪怪的地方抄题目，然后改改就是他出的题了
由于小Y老师要造样例，所以他每抄完第 \(i\) 道题目要 \(w_i\) 分钟
而出题人对每一道题的喜好不同，所以出第 \(i\) 道题小Y老师能得到 \(v_i\) 元
小Y老师有一个列表，写下了每道题需要的时间与能《收割》的钱数
但小Y老师时间不足，所以他来请你帮忙，要你在 \(t\) 分钟内从 \(n\) 道题中选一些题目，使得他在能出完这些题目的条件下骗到最多的钱
输入格式
第一行两个数，\(t\) 与 \(n\)
接下来 \(n\) 行，第 \(i\) 行有两个数，\(w_i\) 与 \(v_i\)
输出格式
小Y老师能骗到多少块钱
样例 #1
样例输入 #1
10 4
2 1
3 3
4 5
7 9
样例输出 #1
12
提示
\(n<30,t<200\)
