测试数据来自 system/1021

作业已超过截止时间，您无法递交本题目。

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

---

【问题描述】

　　有 \(n\) 个物品，物品 \(i\) 的体积为 \(v_i\)，价值为 \(p_i\)。现在要选一些物品装入容量为 \(C\) 的背包（每个物品要么选，要么不选，不能只装一部分），使得背包中物品的价值和最大。

【输入格式】

　　第 1 行是整数 \(n\) 和 \(C\)，表示有 \(n\) 个物品，背包的容量为 \(C\)。
　　接下来的 \(n\) 行，每行两个整数：\(v_i\) 和 \(p_i\)，表示物品 \(i\) 的体积和价值。

【输出格式】

　　一个整数，表示能得到的最大价值。

【输入输出样例1】

　Input

5 100
77 92
12 12
29 87
50 46
99 90

　Output

145

【数据限制】

　\(1 ≤ n ≤ 30\)
　\(1 ≤ v_i,C ≤ 10^9\)
　\(1 ≤ p_i ≤ 10^6\)

【来源】

　　Mr.he