Експрес-доставка#4381

Експрес-доставка

1 секунда

32 мегабайти

Дуже складна

Ваша компанія, Byteland Express, повинна доставити посилки клієнтам, які знаходяться в місті. Місто складається з $2 \cdot 1 0^{9} + 1$ 2 \cdot 10^9 + 1 вулиць, що йдуть з півдня на північ, і $2 \cdot 1 0^{9} + 1$ 2 \cdot 10^9 + 1 вулиць, що йдуть із заходу на схід (усі пронумеровані від $0$ до $2 \cdot 1 0^{9}$ 2 \cdot 10^9). Поштар переміщується від одного перехрестя до сусіднього за одну хвилину. Компанія розташована біля перехрестя вулиць з номерами $x_{c}$ x_c і $y_{c}$ y_c.

Посилки повинні бути доставлені якомога швидше, тому поїздка до клієнта, який знаходиться біля перехрестя $x$ -ї та $y$ -ї вулиці, займе рівно $∣ x_{c} - x ∣ + ∣ y_{c} - y ∣$ |x_c - x| + |y_c - y| хвилин. Час на передачу посилки клієнту незначний, тому під час поїздки до одного клієнта поштар може передати посилку іншому клієнту (але не може вибрати довший маршрут для цього). Ваше завдання — визначити, скільки поштарів потрібно для виконання доставки.

Завдання

Напишіть програму, яка

читає за допомогою SVIO розташування компанії та розташування всіх клієнтів,
знаходить мінімальну кількість поштарів, необхідних для доставки всіх посилок,
записує результат за допомогою SVIO.

Вхідні дані

Перша строка введення містить одне ціле число $N$ ( $1 \leq N \leq 1000000$ 1 \leq N \leq 1000000). Друга строка містить розташування компанії, наступні $N$ строк містять розташування клієнтів. Опис розташування складається з двох цілих чисел: координат $x$ та $y$ ( $0 \leq x, y \leq 2 \cdot 1 0^{9}$ 0 \leq x, y \leq 2 \cdot 10^9). Кожні дві точки (з-поміж компанії або клієнтів) відрізняються за обома координатами (кожне $x$ відрізняється і кожне $y$ відрізняється).

Вихідні дані

В єдиній строкі стандартного виводу запишіть одне ціле число: кількість поштарів, необхідних для доставки посилок усім клієнтам.

Приклади

Приклад 1