5540번 - 夜店 (Night Market) 다국어

太郎くんは，JOI 神社で開かれる夏祭りに行くことにした．

JOI 神社に向かう道に沿って，N 個の夜店が開かれている．それぞれの夜店には，1 から N までの番号が順番についており，遊んだ時の楽しさと遊ぶのにかかる時間がそれぞれ整数で決まっている．夜店 i で遊んだ時の楽しさは A_i で，夜店 i で遊ぶのにかかる時間は B_i である．

また，夏祭りのイベントとして花火大会があり，時刻 S に最も大きな花火が打ち上げられる．太郎くんはこの最も大きな花火を見たいと思っている．

太郎くんは夜店と花火の両方を楽しむために，夏祭りに到着する時刻 0 から夏祭りが終わる時刻 T までの予定を立てることにした．

太郎くんは夜店の中から k 個 (1 ≤ k ≤ N) の夜店を選び，それぞれに対して訪れる時刻を整数で決める．同じ夜店を 2 度選ぶことはできない．選ばれた夜店の番号を小さい順に y₁, y₂, ..., y_k とし，夜店 y_i を訪れる時刻を x_yi とすると，太郎くんは夜店 y_i で時刻 x_yi から時刻 x_yi + B_yi まで遊ぶ．

太郎くんは夜店の番号の小さい順に遊び，同時に 2 つの夜店では遊べない．また，夜店と夜店の間の移動にかかる時間は無視できる．

時刻 T を超えると夏祭りが終わるので，夜店で遊ぶことはできない．また，夜店で遊んでいる間は花火を見ることはできない．ただし，時刻 S がある夜店で遊び始める時刻や遊び終わる時刻であった場合は，太郎くんは花火を見ることができるものとする．

すなわち，予定は以下の条件を満たしていなければならない．

• y₁ < y₂ < ... < y_k
• x_y1, x_y2, ..., x_yk は整数．
• 0 ≤ x_y1 < x_y1 + B_y1 ≤ x_y2 < x_y2 + B_y2 ≤ ... ≤ x_yk < x_yk + B_yk ≤ T
• x_yi < S < x_yi + B_yi となるような i は存在しない．

選ばれた夜店の楽しさ A_y1, A_y2, ..., A_yk の合計を M とする．太郎くんは M ができるだけ大きくなるように予定を立てたいと思っている．

N 個の夜店の情報と時刻 S, T が与えられた時，M の最大値を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

入力の 1 行目には整数 N, T, S が空白を区切りとして書かれており，夜店の数が N 個，夏祭りが終わる時刻が T，最も大きな花火が打ち上げられる時刻が S であることを表す．

続く N 行には夜店の情報が書かれている．入力の i + 1 (1 ≤ i ≤ N) 行目には整数 A_i, B_i が空白を区切りとして書かれており，夜店 i で遊んだ時の楽しさが A_i で，夜店 i で遊ぶのにかかる時間が B_i であることを表す．

また，すべての入力において，１つ以上の予定を立てられることが保証されている．

標準出力に，M の最大値を表す整数を 1 行で出力せよ．

• 1 ≤ N ≤ 3000 夜店の数
• 1 ≤ T ≤ 3000 夏祭りが終わる時刻
• 0 ≤ S ≤ T 最も大きな花火が打ち上げられる時刻
• 0 ≤ A_i ≤ 100000 (= 10⁵) 夜店 i で遊んだ時の楽しさ
• 1 ≤ B_i ≤ 3000 夜店 i で遊ぶのにかかる時間

この例において，

• 夜店 1 を時刻 0 に訪れ，
• 夜店 2 を時刻 9 に訪れ，
• 夜店 4 を時刻 14 に訪れるような予定を立てると，M を最も大きくすることができる．

このとき，M = 8 + 2 + 6 = 16 である．