分数: 366 分
问题陈述
高桥正在超市购物。有 N 商店中的商品,以及 i- 第一项 (1 \leq i \leq N) 的满意度值为 V_i 和价格 C_i 日元。每件商品最多只能购买一次。
高桥有 S 手头有日元。他想准确地花 S 日元。
考虑选购 1 或更多项目 N 项目。如果存在一种方法来选择商品,使得总价恰好是 S 日元,在所有此类选择中找到最大的总满意度。
如果没有选择的商品的总价恰好为 S 日元,产量 -1.
约束
- 1 \leq N \leq 3000
- 1 \leq S \leq 10000
- 1 \leq V_i \leq 10000 (1 \leq i \leq N)
- 1 \leq C_i \leq 10000 (1 \leq i \leq N)
- 所有输入均为整数
输入
N S V_1 C_1 V_2 C_2 \vdots V_N C_N
- 第一行包含一个整数 N 表示项目数和一个整数 S 代表手头的钱数,用空格隔开。
- 的 i- 第行 (1 \leq i \leq N) 以下内容 N 行包含一个整数 V_i 代表满意度值,一个整数 C_i 代表的价格 i- 第一项,以空格分隔。
输出
如果存在选择的方法 1 或更多商品,总价恰好为 S 日元,在单行上输出所选项目的最大总满意度。如果不存在这样的选择,则输出 -1 在一行上。
示例输入 1
3 5 3 2 4 3 1 4
示例输出 1
7
示例输入 2
3 10 1 3 2 3 3 3
示例输出 2
-1
示例输入 3
8 20 10 5 8 7 6 3 12 8 3 4 7 6 9 10 5 2
示例输出 3
31
示例输入 4
15 50 20 8 15 12 30 10 25 15 10 5 18 7 12 9 22 14 8 3 35 20 14 6 9 11 27 13 19 16 11 4
示例输出 4
124
示例输入 5
1 7 5 7
示例输出 5
5