• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

تعداد $n$ خانه در نقاط صحیح مختصات قرار دارند. می‌خواهیم بین هر دو خانه یک سیم تلفن بکشیم. میزان سیم مورد نیاز برای وصل کردن دو خانه به اندازه‌ی فاصله‌ی منهتن آن‌ها است. برنامه‌ای بنویسید که طول بزرگترین سیم موردنیاز را پیدا کند. فاصله‌ی منهتن بین دو نقطه‌ی $(x_i,y_i)$ و $(x_j,y_j)$ برابر است با: $$|x_i - x_j|+|y_i - y_j|$$

ورودی

در خط اول ورودی ابتدا عدد $n$ داده می‌شود. سپس در $n$ خط بعد در هر خط دو عدد که نشان‌دهنده‌ي مختصات خانه‌ی $i$ام است داده می‌شود. $$1 \leq n \leq 100\ 000$$ $$-1\ 000\ 000 \leq x_i,y_i \leq 1\ 000\ 000$$

خروجی

طول بزرگترین سیم مورد استفاده را چاپ کنید.

مثال

ورودی نمونه ۱

5
2 2
4 6
3 8
9 2
5 5

خروجی نمونه ۱

12

دو نقطه $(3, 8)$ و $(9, 2)$ بیشترین فاصله منهتنی را از هم دارند و این فاصله برابر است با: $$|3 - 9| + |8 - 2| = 6 + 6 = 12$$