外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

D - Gathering Nyans

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 300 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんの周りには NN 匹のねこがいます。ねこには 11 から NN までの番号がつけられています。
わりとねこくんは、正の整数の声の大きさ VV を自由に決めて大声で呼びかけ、できるだけ多くのねこを一度に呼びたいと考えています。

ねこ ii はわりとねこくんからの距離 DiD_i と、敏感さ SiS_i を持っています(Di<SiD_i < S_i であることが保証されています)。
声の大きさを VVとしたとき、ねこ ii は以下のように反応します。

  • V<DiV < D_i のとき:声が小さすぎて届かないため、呼ぶことができません。
  • Si≤VS_i \le V のとき:声が大きすぎてねこ ii は驚いて逃げてしまうため、呼ぶことができません。
  • Di≤V<SiD_i \le V < S_i のとき:声が適切に届き、ねこ ii を呼ぶことができます。

わりとねこくんが声の大きさ VV を適切に選んだとき、同時に呼ぶことのできるねこの数の最大値を求めてください。

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤Di<Si≤1091 \le D_i < S_i \le 10^9
  • 入力はすべて整数

入力

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

NN D1S1D_1 \quad S_1 D2S2D_2 \quad S_2 ⋮\vdots DNSND_N \quad S_N

出力

同時に呼ぶことのできるねこの数の最大値を 11 行に出力してください。

サンプル 1

入力

3
2 6
4 8
7 10

出力

2

例えば、わりとねこくんが声の大きさ5でねこを呼んだ時、

  • 1匹目のねこに対して、2≤5<62 \le 5 < 6 であるため、ねこを呼ぶことができます。
  • 2匹目のねこに対して、4≤5<84 \le 5 < 8 であるため、ねこを呼ぶことができます。
  • 3匹目のねこに対して、7>57 > 5 であるため、ねこに声が届かずねこを呼ぶことができません。

このとき呼べるねこは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

参加受付は終了しました。