时间限制：1秒　　内存限制：256M

---

【题目描述】

　　光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。

　　假期里，光光一共有的时间是 \(k\) 小时。在长假前，老师们一共给光光布置了 \(n\) 份作业，第 \(i\) 份作业需要的时间是 \(t_i\) 小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当可能不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。

　　对于一件作业，只有 2 种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第 \(i\) 件作业如果没完成，就要受到 \(p_i\) 个单位的批评。

　　多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？

【输入格式】

　　第一行只有一个数字 \(k\)。
　　第二行只有一个数字 \(n\)。
　　接下来 \(n\) 行，每行两个数字，分别是 \(t_i\) 和 \(p_i\)，两个数字之间用一个空格分开。

【输出格式】

　　仅包含一行，是一个数字，代表了光光最少受到的批评。

【输入输出样例】

　Input

5
3
2 6
1 3
4 7

　Output

6

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤n≤20\)
　　对于 \(100\%\) 的数据，\(1≤n≤500\)，\(1≤k≤100000\)，\(0<t_i≤10000\)，\(1≤p_i≤10000\)

【来源】

　　Mr.he