该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

5.无尽的作业(book)

题目描述

小周为准备这次比赛参加了集训。在集训期间，小周的老师们都非常严厉，还给他布置了一定量的作业。集训期间，小周一共有的时间是k小时。在集训期间前，老师们一共给小周布置了n份作业，第i份作业需要的时间是ti小时。

但是由于老师们互相不商量，因此小周有可能不能完成老师的作业。当不能完成老师的作业时，小周就事后去向老师说明，然后被老师批评一顿了事。

对于一件作业，只有2种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于小周来说，批评的力度是不同的。第i件作业如果没完成，就要受到pi个单位的批评。多次这样之后，小周想要在集训前就知道他至少会受到多少个单位的批评。你能帮助他吗？

输入格式

输入包含以下内容： 第一行只有一个数字k，表示小周一共有的时间数； 第二行只有一个数字n，表示作业数； 接下来n行，每行两个数字，分别是ti和pi，两个数字之间用一个空格分开。

输出格式

输出只包含一行，该行只有一个数字，代表了小周最少受到的批评。

样例输入

5
3
2 6
1 3
4 7

样例输出

6

数据范围

100%的数据中，k≤100000，ti≤10000，pi≤10000； 30%的数据中，n≤20； 100%的数据中，n≤500。

子任务