C - 夏休みの宿題計画 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は夏休みの最終日を迎えました。夏休みが終わるまで残り M 分しかありません。

高橋君には N 個の宿題が残っています。各宿題 i（1 \leq i \leq N）には、完了したときに先生からもらえる評価点 R_i と、完了するのに必要な時間 T_i 分が決まっています。

高橋君はこの M 分の間に、いくつかの宿題を選んで取り組むことができます。ただし、以下の条件があります。

  • 各宿題は、完了するかまったく手をつけないかのいずれかです。途中まで取り組んで部分的に完了させることはできません。取り組む場合は T_i 分をかけて完了させる必要があります。
  • 同じ宿題に複数回取り組むことはできません。すなわち、各宿題を完了できるのは最大 1 回です。
  • 選んだ宿題の必要時間の合計は M 分以下でなければなりません。

高橋君は、これらの条件のもとで、完了した宿題の評価点の合計を最大化したいと考えています。

高橋君が得られる評価点の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10^5
  • 1 \leq R_i \leq 10^9
  • 1 \leq T_i \leq M
  • 入力はすべて整数

入力

N M
R_1 T_1
R_2 T_2
\vdots
R_N T_N
  • 1 行目には、宿題の数 N と、夏休み終了までの残り時間（分） M が空白区切りで与えられる。
  • 続く N 行の i 行目（1 \leq i \leq N）には、宿題 i の評価点 R_i と必要時間 T_i（分）が空白区切りで与えられる。

出力

高橋君が得られる評価点の合計の最大値を 1 行で出力してください。

入力例 1

3 10
6 3
10 5
4 4

出力例 1

16

入力例 2

5 15
100 8
60 5
50 4
40 3
30 2

出力例 2

190

入力例 3

8 1000
1000000000 500
800000000 400
600000000 300
500000000 250
400000000 200
300000000 150
200000000 100
100000000 50

出力例 3

2000000000

Score : 366 pts

Problem Statement

Takahashi has reached the last day of summer vacation. There are only M minutes remaining until summer vacation ends.

Takahashi has N homework assignments left. Each homework assignment i (1 \leq i \leq N) has a fixed evaluation score R_i received from the teacher upon completion, and a required time of T_i minutes to complete.

During these M minutes, Takahashi can choose some homework assignments to work on. However, the following conditions apply:

  • Each homework assignment is either completed entirely or not attempted at all. It is not possible to partially complete an assignment. If he works on it, he must spend T_i minutes to complete it.
  • He cannot work on the same homework assignment multiple times. That is, each homework assignment can be completed at most once.
  • The total required time of the chosen homework assignments must be at most M minutes.

Under these conditions, Takahashi wants to maximize the total evaluation score of completed homework assignments.

Find the maximum total evaluation score that Takahashi can obtain.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10^5
  • 1 \leq R_i \leq 10^9
  • 1 \leq T_i \leq M
  • All inputs are integers

Input

N M
R_1 T_1
R_2 T_2
\vdots
R_N T_N
  • The first line contains the number of homework assignments N and the remaining time until the end of summer vacation (in minutes) M, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the evaluation score R_i and the required time T_i (in minutes) of homework assignment i, separated by a space.

Output

Print the maximum total evaluation score that Takahashi can obtain, on a single line.

Sample Input 1

3 10
6 3
10 5
4 4

Sample Output 1

16

Sample Input 2

5 15
100 8
60 5
50 4
40 3
30 2

Sample Output 2

190

Sample Input 3

8 1000
1000000000 500
800000000 400
600000000 300
500000000 250
400000000 200
300000000 150
200000000 100
100000000 50

Sample Output 3

2000000000