Петрик руйнує міста
Limits: 2 sec., 256 MiB
Вуйко Сергій, який працює в Міністерстві освіти і науки України, подбав про інфраструктуру для ЗНО.
Є \(n\) міст на координатній прямій. \(i\)-е місто розташоване в точці з координатою \(x_i\). Також кожне місто має параметр \(w_i\) — дальність обміну повідомленнями. Між містами \(i\) та \(j\) можна передати повідомлення, якщо відстань між ними не перевищує \(w_i + w_j\).
Злий Петрик хоче зірвати проведення ЗНО. Для цього він вирішив підірвати деякі міста так, щоб між жодними двома містами, що залишилися, не можна було передавати повідомлення. Оскільки вибухівка дорога, то Петрик хоче підірвати якомога менше міст.
Порахуйте, яку мінімальну кількість повинен підірвати Петрик, щоб зірвати проведення ЗНО.
Input
У першому рядку задано ціле число \(n\) — кількість міст.
Кожен з наступних \(n\) рядків містить по два цілих числа \(x_i\), \(w_i\) — координату та дальність обміну повідомленнями кожного міста.
Output
В одному рядку виведіть ціле число — мінімальну кількість міст, яку потрібно підірвати Петрику.
Constraints
\(1 \le n \le 10^5\),
\(0 \le x_i, w_i \le 10^9\),
для 9 тестів виконується додаткове обмеження:
\(1 \le n \le 10\).
Samples
Input (stdin) | Output (stdout) |
---|---|
5 4 2 11 1 47 7 7 3 47 4 | 2 |
Notes
У прикладі Петрик може підірвати міста 3 й 4. Це не єдиний спосіб досягнути оптимальної відповіді.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|