分数: 366 分
问题陈述
高桥来到了一家购物中心。商场有卖的 N 项目类型,其中 i- 第一件商品的价格为 C_i 日元和满意度值 V_i 高桥。
高桥目前有 S 日元,但他必须保留 T 日元作为生活费。换句话说,购买物品的总金额不得超过 S - T 日元。
每件商品最多只能购买一次。求高桥可以获得的最大总满意度。
约束
- 1 \leq N \leq 2000
- 1 \leq T \leq S \leq 10^5
- 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N S T C_1 V_1 C_2 V_2 : C_N V_N
- 第一行包含 N,项目类型的数量, S,高桥的总金额,以及 T,作为生活费保留的金额,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个项目的信息。
- 的 (1 + i)第行包含 C_i,价格 i- 第一项,以及 V_i,该项目的满意度值,以空格分隔。
输出
在一行中打印高桥可以获得的最大总满意度。
示例输入 1
3 100 30 30 50 40 60 50 80
示例输出 1
110
示例输入 2
3 50 50 10 100 20 200 30 300
示例输出 2
0
示例输入 3
8 500 100 100 200 150 300 200 500 80 150 120 250 250 600 50 100 180 400
示例输出 3
900
示例输入 4
15 10000 3000 500 1200 1200 3500 800 2000 1500 4000 300 700 2000 5500 700 1800 900 2400 1100 3000 600 1500 1800 4800 400 1000 1300 3600 250 600 950 2600
示例输出 4
19200
示例输入 5
1 1 1 1 1000000000
示例输出 5
0