← 返回题目列表

AtCoder · awc0075_c

C. 在预算范围内购物

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

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