C - お姉ちゃんって呼んで (Call me sister) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんは少し疲れたので、近くにあった喫茶店で休むことにした。
ここで、joisinoお姉ちゃんは、あるウェイトレスがとても気に入ったので、彼女に「お姉ちゃん」と呼んでもらいたいと思った。
しかし、彼女に「お姉ちゃん」と呼んでもらえるかどうかは、彼女の機嫌にかかわっている。

これからこの喫茶店では、N個の出来事が起こる。
それぞれの出来事には1～Nまでの番号が割り振られていて、出来事i(1≦i≦N)は、時刻T_iに起こり、ウェイトレスの機嫌にK_iが足される。
なお、同じ時刻に二つ以上の出来事が起こることはない
そして、ウェイトレスの機嫌がM以上の時だけ、お姉ちゃんと呼んでもらうことができる。
現在の時刻は0であり、現在のウェイトレスの機嫌は0である。

joisinoお姉ちゃんは、時刻Sにこの喫茶店を出る。
joisinoお姉ちゃんは、店を出るまでの間に「お姉ちゃん」と呼んでもらえる時間がどれだけあるのか知りたいと思い、それを求めるプログラムを作成することにした。
なお、joisinoお姉ちゃんがどのようにして、これから起こる出来事の情報を手に入れたのかは謎である。

入力

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

N M
S
T_1 K_1
T_2 K_2
:
T_N K_N
  • 1行目には、これから起こる出来事の数N(1≦N≦1000)と、お姉ちゃんと呼んでもらえる機嫌の最低値M(0≦M≦10000)が空白区切り書かれている。
  • 2行目には、joisinoお姉ちゃんが喫茶店を出る時刻S(2≦S≦10000)が書かれている。
  • 3行目から続くN行のうちi行目では、これから起こる出来事の情報として、整数T_i(0＜T_i＜S)と、整数K_i(-10000≦K_i＜0,0＜K_i≦10000)が空白区切りで書かれている。
  • i≠jにおいて、T_i≠T_jが保障されている。

配点

この問題に部分点はない。正解すると60点が得られる。

出力

お姉ちゃんと呼んでもらえる時間の合計を1行で出力せよ。
また、出力の末尾には改行を入れること。

入力例1

5 20
20
5 16
8 -4
3 9
18 2
12 -3

出力例1

9
  • 時刻5から時刻12までの7と、時刻18から、喫茶店を出る時刻20までの2の間で、機嫌が20以上となっているため、その合計である9を出力する。