003 - 夜店 (Night Market)
時間制限 1 秒 / メモリ制限 128 MB / 得点 100 / x 2 /
問題
太郎くんは，JOI 神社で開かれる夏祭りに行くことにした．
JOI 神社に向かう道に沿って，N 個の夜店が開かれている．それぞれの夜店には，1 から N までの番号が順番についており，遊んだ時の楽しさと遊ぶのにかかる時間がそれぞれ整数で決まっている．夜店 i で遊んだ時の楽しさは Ai で，夜店 i で遊ぶのにかかる時間は Bi である．
また，夏祭りのイベントとして花火大会があり，時刻 S に最も大きな花火が打ち上げられる．太郎くんはこの最も大きな花火を見たいと思っている．
太郎くんは夜店と花火の両方を楽しむために，夏祭りに到着する時刻 0 から夏祭りが終わる時刻 T までの予定を立てることにした．
太郎くんは夜店の中から k 個 (1 ≤ k ≤ N) の夜店を選び，それぞれに対して訪れる時刻を整数で決める．同じ夜店を 2 度選ぶことはできない．選ばれた夜店の番号を小さい順に y1, y2, ..., yk とし，夜店 yi を訪れる時刻を xyi とすると，太郎くんは夜店 yi で時刻 xyi から時刻 xyi + Byi まで遊ぶ．
太郎くんは夜店の番号の小さい順に遊び，同時に 2 つの夜店では遊べない．また，夜店と夜店の間の移動にかかる時間は無視できる．
時刻 T を超えると夏祭りが終わるので，夜店で遊ぶことはできない．また，夜店で遊んでいる間は花火を見ることはできない．ただし，時刻 S がある夜店で遊び始める時刻や遊び終わる時刻であった場合は，太郎くんは花火を見ることができるものとする．
すなわち，予定は以下の条件を満たしていなければならない．
- y1 < y2 < ... < yk
- xy1, xy2, ..., xyk は整数．
- 0 ≤ xy1 < xy1 + By1 ≤ xy2 < xy2 + By2 ≤ ... ≤ xyk < xyk + Byk ≤ T
- xyi < S < xyi + Byi となるような i は存在しない．
選ばれた夜店の楽しさ Ay1, Ay2, ..., Ayk の合計を M とする．太郎くんは M ができるだけ大きくなるように予定を立てたいと思っている．
課題
N 個の夜店の情報と時刻 S, T が与えられた時，M の最大値を求めるプログラムを作成せよ．
制限
1 ≤ N ≤ 3 000 夜店の数
1 ≤ T ≤ 3 000 夏祭りが終わる時刻
0 ≤ S ≤ T 最も大きな花火が打ち上げられる時刻
0 ≤ Ai ≤ 100 000 (= 105) 夜店 i で遊んだ時の楽しさ
1 ≤ Bi ≤ 3 000 夜店i で遊ぶのにかかる時間
入力
標準入力から以下の入力を読み込め．
入力の1 行目には整数 N, T, S が空白を区切りとして書かれており，夜店の数が N 個，夏祭りが終わる時刻が T，最も大きな花火が打ち上げられる時刻が S であることを表す．
続く N 行には夜店の情報が書かれている．入力の i + 1 (1 ≤ i ≤ N) 行目には整数 Ai, Bi が空白を区切りとして書かれており，夜店 i で遊んだ時の楽しさが Ai で，夜店 i で遊ぶのにかかる時間が Bi であることを表す．
また，すべての入力において，１つ以上の予定を立てられることが保証されている．
出力
標準出力に，M の最大値を表す整数を1 行で出力せよ．
採点基準
採点用データのうち，
配点の 10 %分については，N ≤ 20 を満たす．
配点の 20 %分については，S = 0 を満たす．
配点の 30 %分については，これら 2 つの条件の少なくとも一方を満たす．また，これら 2 つの条件の両方を満たすような採点用データはない．
入出力例
入力例 1
5 20 14 8 9 2 4 7 13 6 3 5 8
出力例 1
16
この例において，
夜店 1 を時刻 0 に訪れ，
夜店 2 を時刻 9 に訪れ，
夜店 4 を時刻 14 に訪れるような予定を立てると，M を最も大きくすることができる．
このとき，M = 8 + 2 + 6 = 16 である．