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

---

【题目描述】

　　给出 \(N\) 个物品，第 \(i\) 个物品的体积为 \(v[i]\)，价值为 \(p[i]\)，现在需要选择一些物品装满容量为 \(C\) 的背包，所能获得的最大价值，如果不能装满，则输出-1。

【输入格式】

　　第 1 行：两个整数 \(C\) 和 \(N\) 。
　　接下来的 \(N\) 行：每行两个整数，表示 \(v[i]\) 和 \(p[i]\) 。

【输出格式】

　　一个整数，表示解，若不能装满，则输出-1。

【输入输出样例1】

　Input

10 5
2 2
8 7
3 3
5 4
7 8

　Output

11

【输入输出样例2】

　Input

16 5
3 3
1 3
2 1
5 4
4 6

　Output

-1

【数据限制】

　　\(100\%\) 的数据满足：\(2≤v[i]≤C≤200\)，\(1≤p[i]≤1,000,000\)。

【来源】

　　Mr.he