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

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

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

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

太郎くんは夜店の中から k 個 (1 \leqq k \leqq N) の夜店を選び，それぞれに対して訪れる時刻を整数で決める．同じ夜店を 2 度選ぶことはできない．選ばれた夜店の番号を小さい順に y_1,y_2,\ldots,y_k とし，夜店 y_i を訪れる時刻を x_{y_i} とすると，太郎くんは夜店 y_i で時刻 x_{yi} から時刻 x_{y_i} + B_{y_i} まで遊ぶ．

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

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

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

• y_1 < y_2 < \ldots < y_k
• x_{y_1},x_{y_2},\ldots , x_{y_k} は整数．
• 0\leqq x_{y_1} < x_{y_1} + B_{y_1} \leqq x_{y_2} < x_{y_2} + B_{y_2} \leqq \ldots \leqq x_{y_k} < x_{y_k} + B_{y_k} \leqq T
• x_{y_i} < S < x_{y_i}+B_{y_i} となるような i は存在しない．

選ばれた夜店の楽しさ A_{y_1},A_{y_2},\ldots,A_{y_k} の合計をを M とする．太郎くんは M ができるだけ大きくなるように予定を立てたいと思っている．

課題

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

制限

採点基準

採点用データのうち，

配点の 10 %分については，N \leqq 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 である．