← 返回题目列表

AtCoder · awc0052_c

C. 购物挑战

中文机器翻译题面 查看原题

分数: 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