Байрактар
Обмеження: 3 сек., 256 МіБ
Зеник — оператор Байрактара. Розвідка повідомила, що колона окупантів з n грузовиків планує підірвати мости, аби заповільнити наступ української армії. Відомо, що і-тий грузовик зараз знаходиться в кооринаті ai і містить bi вибухівки. Якщо вибухне i-тий грузовик, то також вибухнуть всі грузовики на проміжку [ai−bi,ai+bi]. Нажаль у байрактара, яким керує Зеник залишилася лише одна ракета слабкої потужності і тому вона знищує лише ціль в яку попаде. Так як Зеник дуже вправно керує байрактаром, то він може попасти ракетою у будь-який грузовик. Допоможіть Зенику та скажіть яку максимальнку кількість грузовиків він зможе підірвати.
Вхідні дані
У першому рядку задно одне ціле число n — кількість вантажівок з вибухівкою.
У другому рядку задано n цілих чисел ai — координата і-тої вантажівки.
У третьому рядку задано n цілих чисел bi — кількість вибухівки в і-тій вантажівці.
Вихідні дані
У єдиному рядку виведіть одне ціле число — максимальна кількість грузовиків, які може підірвати Зеник.
Обмеження
1≤n≤105,
0≤ai,bi≤109, усі ai різні.
Оцінювання задачі складається із наступних блоків:
1 бал — перший приклад з умови,
1 бал — другий приклад з умови,
6 балів — блок тестів у яких 1≤n≤100,
7 балів — блок тестів у яких 1≤n≤3000,
10 балів — блок тестів у яких 1≤n≤105,
Бали за блок ви отримаєте, лише якщо дасте правильну відповідь на всі тести з блоку.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 5 1 5 7 8 9 3 2 1 2 1 | 4 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 6 3 2 1 7 5 9 1 0 1 2 0 0 | 3 |
Примітки
У першому прикладі найкраще підірвати другий грузовик, який безпосередньо підірве третій, що в свою чергу підірве четвертий, який підірве п’ятий. У результаті буде підірвано 4 грузовики.
У другому прикладі найкраще підірвати четвертий грузовик, що знаходиться в координаті 7, який безпосередньо підірве п’ятий та шостий грузовики. У результаті буде підірвано 3 грузовики.