У похід!#11059
У країні Смішариків — новий сезон! Тепер всі герої відправляються в похід. Для цього їм необхідно зустрітися в одній точці, а вже звідти рушити підкорювати світ. Лосяш, який координує дії Смішариків, знає координати всіх учасників походу. Допоможіть йому визначити, яка мінімальна кількість секунд знадобиться, щоб всі Смішарики зібралися разом.
Спочатку кожен Смішарик знаходиться у вузлі цілочисельної сітки. Якщо Смішарик стоїть у точці , то за одну секунду він може переміститися в одну з точок (x, y + 1), (x + 1, y), (x - 1, y), (x, y - 1) або залишитися на місці.
У першому рядку задано одне ціле число n~(1 \le n \le 200000) — кількість Смішариків. У наступних рядках вказані їх початкові позиції. Кожна позиція задається двома цілими числами x_i і y_i~(-10^{18} \le x_i, y_i \le 10^{18}).
Виведіть мінімальну кількість секунд, необхідну для того, щоб всі Смішарики зібралися в одній точці.
Приклад 1
Приклад 2
Приклад 3