/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君はショッピングモールにやってきました。モールには N 種類の商品が売られており、 i 番目の商品の価格は C_i 円で、高橋君にとっての満足度は V_i です。
高橋君は現在 S 円を持っていますが、このうち T 円は生活費として残しておかなければなりません。つまり、商品の購入に使える金額の合計は S - T 円以下でなければなりません。
各商品は最大 1 個しか購入できません。高橋君が得られる満足度の合計の最大値を求めてください。
制約
- 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
- 1 行目には、商品の種類数を表す N 、高橋君の所持金を表す S 、生活費として残す金額を表す T が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各商品の情報が与えられる。
- 1 + i 行目では、 i 番目の商品の価格を表す C_i と、その商品の満足度を表す V_i が、スペース区切りで与えられる。
出力
高橋君が得られる満足度の合計の最大値を 1 行で出力せよ。
入力例 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
Score : 366 pts
Problem Statement
Takahashi has come to a shopping mall. The mall sells N types of items, where the i-th item has a price of C_i yen and a satisfaction value of V_i for Takahashi.
Takahashi currently has S yen, but he must keep T yen as living expenses. In other words, the total amount spent on purchasing items must be at most S - T yen.
Each item can be purchased at most once. Find the maximum total satisfaction Takahashi can obtain.
Constraints
- 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)
- All input values are integers
Input
N S T C_1 V_1 C_2 V_2 : C_N V_N
- The first line contains N, the number of item types, S, Takahashi's total money, and T, the amount to keep as living expenses, separated by spaces.
- From the 2nd line to the (N + 1)-th line, the information for each item is given.
- The (1 + i)-th line contains C_i, the price of the i-th item, and V_i, the satisfaction value of that item, separated by spaces.
Output
Print the maximum total satisfaction Takahashi can obtain, in a single line.
Sample Input 1
3 100 30 30 50 40 60 50 80
Sample Output 1
110
Sample Input 2
3 50 50 10 100 20 200 30 300
Sample Output 2
0
Sample Input 3
8 500 100 100 200 150 300 200 500 80 150 120 250 250 600 50 100 180 400
Sample Output 3
900
Sample Input 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
Sample Output 4
19200
Sample Input 5
1 1 1 1 1000000000
Sample Output 5
0