B39 - Taro's Job Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

重要：この問題は、書籍『競技プログラミングの鉄則』の 6.4 節と 8.3 節で二度扱っています。 6.4 節の解法では、部分点しか取れない可能性があることに注意してください（8.3 節の解法では満点を取ることができます）

問題文

太郎君は今日から D 日間、仕事をしようと思いました。 仕事の選択肢は N 個あり、i 個目の仕事は X_i 日目以降になれば選ぶことができ、完了すれば Y_i 円もらえます。 1 つの仕事をするのに 1 日かかるとき、太郎君は最大何円を稼ぐことが出来ますか。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 2000
  • 1 \leq X_i \leq D
  • 1 \leq Y_i \leq 10^6
  • 入力はすべて整数

(2022/10/05 2:00 追記) D の制約を 365 から 2000 に引き上げ、テストケースを再作成しています。

部分点

N \leq 2000 を満たすテストケースにすべて正解した場合、200 点が与えられます。

入力

入力は以下の形式で標準入力から与えられます。 

N D
X_1 Y_1
\vdots
X_N Y_N

出力

答えを整数で出力してください。

入力例 1

5 4
1 1
2 4
2 3
3 4
4 2

出力例 1

12

1 個目、2 個目、4 個目、3 個目の順に仕事をすると 1+4+4+3=12 円得ることができ、これが最大です。