太郎くんは，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 がある夜店で遊び始める時刻や遊び終わる時刻であった場合は，太郎くんは花火を見ることができるものとする．
すなわち，予定は以下の条件を満たしていなければならない．
選ばれた夜店の楽しさAy1, Ay2, ... Ayk の合計をM とする．太郎くんはM ができるだけ大きくなるように予定を立てたいと思っている．
N 個の夜店の情報と時刻S, T が与えられた時，M の最大値を求めるプログラムを作成せよ．
1 ≤ N ≤ 3000 夜店の数
1 ≤ T ≤ 3000 夏祭りが終わる時刻
0 ≤ S ≤ T 最も大きな花火が打ち上げられる時刻
0 ≤ Ai ≤ 100000 (= 105) 夜店i で遊んだ時の楽しさ
1 ≤ Bi ≤ 3000 夜店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 つの条件の両方を満たすような採点用データはない．
5 20 14 8 9 2 4 7 13 6 3 5 8
16
この例において，
夜店1 を時刻0 に訪れ，
夜店2 を時刻9 に訪れ，
夜店4 を時刻14 に訪れるような予定を立てると，M を最も大きくすることができる．
このとき，M = 8 + 2 + 6 = 16 である．
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。