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

众所周知，战士是叠甲最慢的职业。
麦格尼·铜须有N个法力水晶和M种不同的法术。这次他得到了游学者周卓的帮助，所以这M种法术均可以无限次使用。每次使用法术会消耗一定量的法力水晶并获得一定量的护甲。他想知道如何使用这些法术才能使他获得最多的护甲。
第1行输入两个正整数N和M，0 < N, M <= 10000,
第2行至第M+1行输入分别M种法术的费用及使用之后获得的护甲。
输出一个正整数，即麦格尼·铜须能够获得的最多的护甲量。

输入样例

10 4
2 1
3 3
4 5
7 9

输出样例

12