题目描述

高桥君在超市购物。店里有 $N$ 件商品，第 $i$ 件商品（$1 \leq i \leq N$）有满意度 $V_i$ 和价格 $C_i$ 日元。每件商品最多购买一次。

高桥君手头有 $S$ 日元，他希望恰好花完这 $S$ 日元。

考虑从 $N$ 件商品中选择至少 1 件购买。如果存在一种选择方式使得商品总价恰好为 $S$ 日元，求所有满足条件的选择中满意度总和的最大值。

如果不存在总价恰好为 $S$ 日元的选择方式，输出 $-1$。

输入格式

第一行两个整数 $N, S$。

接下来 $N$ 行，每行两个整数 $V_i, C_i$，表示第 $i$ 件商品的满意度和价格。

输出格式

如果存在总价恰好为 $S$ 日元的购买方式，输出满意度总和的最大值；否则输出 $-1$。

3 5
3 2
4 3
1 4

7

3 10
1 3
2 3
3 3

-1

8 20
10 5
8 7
6 3
12 8
3 4
7 6
9 10
5 2

31

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

124

1 7
5 7

5

数据范围

• $1 \leq N \leq 3000$
• $1 \leq S \leq 10000$
• $1 \leq V_i \leq 10000$
• $1 \leq C_i \leq 10000$
• 输入均为整数

来源

AtCoder AWC 0052C