C - Shopping with Remaining Time Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はデパートの閉店セールに行く予定でしたが、うっかり昼寝をしてしまい、到着が遅れてしまいました。

デパートのセールは時刻 0 分に開始され、時刻 T 分に閉店します。高橋君がデパートに到着するのは時刻 S 分です（ 0 \leq S \leq T ）。高橋君は到着した時刻 S 分から閉店時刻 T 分までの残り T - S 分間で買い物をすることができます。

セール会場には N 個の商品があります。 i 番目の商品（ 1 \leq i \leq N ）を購入するには C_i 分の購入手続き時間がかかり、購入すると P_i 円のお得さを得られます。各商品は最大 1 個まで購入できます。

高橋君は一度に 1 つの商品の購入手続きしか進めることができません。ある商品の購入手続きが完了したら直ちに次の商品の購入手続きを開始できます。購入手続き以外に時間はかかりません。また、購入手続きを途中で中断することはできず、手続きは閉店時刻までに完了しなければなりません。

したがって、購入する商品の集合を A としたとき、購入手続き時間の合計が残り時間以下、すなわち \displaystyle\sum_{i \in A} C_i \leq T - S を満たす必要があります。

この条件のもとで、高橋君が得られるお得さの合計 \displaystyle\sum_{i \in A} P_i の最大値を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq T \leq 10^4
  • 0 \leq S \leq T
  • 1 \leq C_i \leq 10^4
  • 1 \leq P_i \leq 10^5
  • 入力はすべて整数である

入力

N T S
C_1 P_1
C_2 P_2
\vdots
C_N P_N
  • 1 行目には、商品の個数を表す整数 N 、閉店時刻（分）を表す整数 T 、高橋君の到着時刻（分）を表す整数 S が、スペース区切りで与えられる。
  • 2 行目から N 行では、各商品の情報が与えられる。
  • 1 + i 行目では、 i 番目の商品の購入手続きにかかる時間（分）を表す整数 C_i と、得られるお得さ（円）を表す整数 P_i が、スペース区切りで与えられる。

出力

高橋君が得られるお得さの合計の最大値を、整数で 1 行に出力せよ。

入力例 1

3 10 7
2 100
3 150
4 200

出力例 1

150

入力例 2

5 100 85
5 300
8 500
10 600
3 200
7 450

出力例 2

950

入力例 3

8 5000 4970
12 800
9 550
15 900
6 400
8 600
10 700
5 350
3 200

出力例 3

2100

Score : 366 pts

Problem Statement

Takahashi was planning to go to a department store's closing sale, but he accidentally took a nap and arrived late.

The department store sale starts at time 0 minutes and the store closes at time T minutes. Takahashi arrives at the department store at time S minutes (0 \leq S \leq T). He can shop during the remaining T - S minutes from his arrival time S until the closing time T.

There are N items at the sale venue. Purchasing the i-th item (1 \leq i \leq N) requires C_i minutes of purchase processing time, and buying it yields a savings value of P_i yen. Each item can be purchased at most once.

Takahashi can only process the purchase of one item at a time. Once the purchase processing of an item is completed, he can immediately start processing the next item. No time is required other than purchase processing. Also, purchase processing cannot be interrupted midway, and all processing must be completed by the closing time.

Therefore, if A is the set of items to purchase, the total purchase processing time must not exceed the remaining time, i.e., \displaystyle\sum_{i \in A} C_i \leq T - S must be satisfied.

Under this condition, find the maximum total savings value \displaystyle\sum_{i \in A} P_i that Takahashi can obtain.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq T \leq 10^4
  • 0 \leq S \leq T
  • 1 \leq C_i \leq 10^4
  • 1 \leq P_i \leq 10^5
  • All inputs are integers

Input

N T S
C_1 P_1
C_2 P_2
\vdots
C_N P_N
  • The first line contains three space-separated integers: N representing the number of items, T representing the closing time (in minutes), and S representing Takahashi's arrival time (in minutes).
  • The next N lines contain the information for each item.
  • The (1 + i)-th line contains two space-separated integers: C_i representing the purchase processing time (in minutes) for the i-th item, and P_i representing the savings value (in yen) obtained from it.

Output

Output the maximum total savings value that Takahashi can obtain, as an integer on a single line.

Sample Input 1

3 10 7
2 100
3 150
4 200

Sample Output 1

150

Sample Input 2

5 100 85
5 300
8 500
10 600
3 200
7 450

Sample Output 2

950

Sample Input 3

8 5000 4970
12 800
9 550
15 900
6 400
8 600
10 700
5 350
3 200

Sample Output 3

2100