C - AtColor 解説 /

実行時間制限: 3 sec / メモリ制限: 256 MB

問題文

　AtColor社は，0 から 1,000,000 まで 1,000,001 通りの濃さがある灰色の絵の具を販売することにしました．0 が最も黒く，1,000,000 が最も白い絵の具です．

　しかし，途方も無い数の濃さのバリエーションがある一方，消費者には細かい違いが分からないということが判明しました．これを知ったAtColor社は，売れない濃さの絵の具を生産するのはやめて，最も人気のある濃さの色の絵の具1つだけを販売することにしました．

　AtColor社は上記を達成するために，最も人気な絵の具がどのくらい売れるかをアンケート調査で調べることにしました． AtColor社がどの範囲の濃さの絵の具なら購入したいかというアンケートを消費者に対して行ったところ， 「a ≦ x ≦ b を満たす濃さ x の絵の具ならば購入する」という形式の情報が n 件得られました．

　あなたの仕事は，これらの情報から，最も多くの消費者に購入される濃さの絵の具について，その絵の具を購入する消費者の数を出力するプログラムを作ることです．

入力

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

n
a_{1}\ b_{1}
a_{2}\ b_{2}
:
a_{n}\ b_{n}
  • 1 行目には，アンケート情報の数 n (1 ≦ n ≦ 100,000) が与えられる．
  • 続く 2 行目から n行は，各アンケート情報を表す． a_i,b_i(0≦a_i≦b_i≦1,000,000) はそれぞれ i 番目のアンケート情報における濃さの下限と上限(端を含む)を表す整数で，空白区切りで与えられる．

部分点

この問題には2つのデータセットがあり，データセット毎に部分点が設定されている．

  • 1≦n≦2,000 を満たすデータセット 1 に正解した場合は 30 点が与えられる．
  • 追加制約のないデータセット 2 に正解した場合は，上記のデータセットとは別に 70 点が与えられる．

出力

最も多くの消費者に購入される濃さの絵の具について，それを購入する消費者の数を 1 行に出力せよ．出力の末尾に改行を入れること．

入力例1

4
0 2
2 3
2 4
5 6

出力例1

3
  • 濃さ 0,1,4,5,6 の絵の具は，1人の消費者によって購入してもらえます．
  • 濃さ 2 の絵の具は，3人の消費者によって購入してもらえます．
  • 濃さ 3 の絵の具は，2人の消費者によって購入してもらえます．
  • 他の濃さの絵の具は誰にも購入してもらえません．

よって，3 を出力します．

入力例2

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

出力例2

4