AT_joi2023ho_b 宣伝 2 (Advertisement 2)

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 国の住人全員が理恵さんの本を手に入れるために，最小で何人に献本する必要があるかを求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ X_1 $ $ E_1 $ $ X_2 $ $ E_2 $ $ \vdots $ $ X_N $ $ E_N $

標準出力に，理恵さんが献本すべき住人の人数の最小値を $ 1 $ 行で出力せよ． ---

### 小課題 1. ( $ 10 $ 点) $ E_1 = E_2 = \cdots = E_N $ ． 2. ( $ 23 $ 点) $ N \leqq 16 $ ． 3. ( $ 36 $ 点) $ N \leqq 1\,000 $ ． 4. ( $ 31 $ 点) 追加の制約はない． --- ### Sample Explanation 1 たとえば次のように献本すると，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 $ の制約を満たす． --- ### Sample Explanation 2 この入出力例はすべての小課題の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 2, 3, 4 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．