問題文
わりとねこくんの周りには 匹のねこがいます。ねこには から までの番号がつけられています。
わりとねこくんは、正の整数の声の大きさ を自由に決めて大声で呼びかけ、できるだけ多くのねこを一度に呼びたいと考えています。
ねこ はわりとねこくんからの距離 と、敏感さ を持っています( であることが保証されています)。
声の大きさを としたとき、ねこ は以下のように反応します。
- のとき:声が小さすぎて届かないため、呼ぶことができません。
- のとき:声が大きすぎてねこ は驚いて逃げてしまうため、呼ぶことができません。
- のとき:声が適切に届き、ねこ を呼ぶことができます。
わりとねこくんが声の大きさ を適切に選んだとき、同時に呼ぶことのできるねこの数の最大値を求めてください。
制約
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
出力
同時に呼ぶことのできるねこの数の最大値を 行に出力してください。
サンプル 1
入力
3
2 6
4 8
7 10
出力
2
例えば、わりとねこくんが声の大きさ5でねこを呼んだ時、
- 1匹目のねこに対して、 であるため、ねこを呼ぶことができます。
- 2匹目のねこに対して、 であるため、ねこを呼ぶことができます。
- 3匹目のねこに対して、 であるため、ねこに声が届かずねこを呼ぶことができません。
このとき呼べるねこは2匹で、これは呼ぶことのできるねこの最大値であるため、2を出力します。
サンプル 2
入力
4
1 3
3 5
5 7
7 9
出力
1
サンプル 3
入力
5
32 48
2 33
28 31
40 46
13 18
出力
2
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする