問題文

JOI 国には N 人の住人がおり，1 から N までの番号が付けられている． 住人 i (1 \leqq i \leqq N) は数直線上の座標 X_i に住んでおり，その影響力は E_i である．同じ座標に複数の住人が住んでいることもある． 影響力が高い住人ほど宣伝効果が大きい一方で，本を買うのに慎重になる．

理恵さんは情報科学の本を出版した．本を多くの人に買ってもらうため，何人かの住人に献本をすることができる． 住民 i (1 \leqq i \leqq N) に献本した場合，住人 i は理恵さんの本を手に入れる． さらに，まだ理恵さんの本を持っていない住人のうち，次の条件を満たすようなすべての住人 j (1 \leqq j \leqq N) は理恵さんの本を買って手に入れる．

• 住人 i と住人 j との数直線上での距離が E_i - E_j 以下である．すなわち |X_i - X_j| \leqq E_i - E_j である．

もし理恵さんの本が JOI 国のすべての住人に読まれれば，情報オリンピックの知名度は大きく向上するだろう． JOI 国の住人全員が理恵さんの本を手に入れるために，最小で何人に献本する必要があるかを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 500\,000．
• 1 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq E_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (10 点) E_1 = E_2 = \cdots = E_N．
2. (23 点) N \leqq 16．
3. (36 点) N \leqq 1\,000．
4. (31 点) 追加の制約はない．

入力例 1

4
4 2
2 3
3 4
6 5

出力例 1

2

たとえば次のように献本すると，JOI 国の住人全員が理恵さんの本を手に入れることができる．

• 住人 3 に献本する．

  • |X_3 - X_1| = 1, E_3 - E_1 = 2 より，住人 1 は理恵さんの本を買って手に入れる．
  • |X_3 - X_2| = 1, E_3 - E_2 = 1 より，住人 2 は理恵さんの本を買って手に入れる．
  • |X_3 - X_4| = 3, E_3 - E_4 = -1 より，住人 4 は理恵さんの本を買わない．

  よって，住人 1, 2, 3 が理恵さんの本を手に入れることになる．

• 住人 4 に献本する．住人 4 以外の住人はいずれも既に理恵さんの本を手に入れているので，これで JOI 国の住人全員が理恵さんの本を手に入れたことになる．

2 人未満への献本で JOI 国の住人全員が理恵さんの本を手に入れるようにすることはできないので，2 を出力する．
この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 2

3
7 10
10 10
7 10

出力例 2

2

この入出力例はすべての小課題の制約を満たす．

入力例 3

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

出力例 3

5

この入力例は小課題 2, 3, 4 の制約を満たす．