Юниорская олимпиада по информатике 2021 года за 8 класс | Казахстанские олимпиады

Задача B. Сбор стаи

В Казахстане живет одна популярная стая волков. Сейчас они блуждают по плоскости и разошлись в разные стороны для исследования местности. Всего в стае $N$ волков и координата $i$-го волка ($x_i$,$y_i$). За одну секунду вы можете приказать одному волку перейти из координаты ($x$,$y$) в одном из четырех направлений ($x$,$y−1$), ($x$,$y+1$), ($x−1$,$y$) или ($x+1$,$y$). Так как местность уже исследована стае пора собраться вместе в одной точке и поделиться собранной информацией. Вам надо собрать всех волков в одной точке за кратчайшее возможное время. Выведите минимальное количество секунд требующиеся для этого.

Формат входного файла

Первая строка содержит целое число $N$ ($1 \leq N \leq 10^5$). Следующие $N$ строк содержат по $2$ целых числа $x_i,y_i$ $(1 \leq x_i, y_i \leq 10^5)$ координаты $i$-го волка.

Формат выходного файла

Выведите минимальное количество секунд нужное для сбора стаи.

Система оценки

Примеры

Входные данные

3
1 3
2 1
3 2

Выходные данные

4

Примечание

В первом тесте самое оптимальное место сбора координата (2, 2). Первый волк доберется туда за 2 секунды, второй волк за 1 секунду, третий за 1 секунду. 2+1+1=4.