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

---

【题目描述】

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

【输入格式】

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

【输出格式】

　　一个整数，表示问题的解，如果无解，则输出-1。

【输入输出样例1】

　Input

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

　Output

9

【输入输出样例2】

　Input

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

　Output

-1

【数据限制】

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

【来源】

　　Mr.he