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を出力する。