تقف أبقار Farmer John وعددها $N$ في مواقع مختلفة $(x_1, y_1) \ldots (x_n, y_n)$ على مزرعته ثنائية الأبعاد ($1 \leq N \leq 100,000$، و$x_i$ و$y_i$ أعداد صحيحة موجبة فردية لا تتجاوز $1,000,000$). يريد FJ تقسيم الحقل بسياج طويل، غير محدود عمليًا، باتجاه شمال-جنوب ومعادلته $x=a$. سيكون $a$ عددًا صحيحًا زوجيًا لضمان ألا يمر السياج بموقع أي بقرة. ويريد أيضًا سياجًا طويلًا، غير محدود عمليًا، باتجاه شرق-غرب ومعادلته $y=b$، حيث $b$ عدد صحيح زوجي. يتقاطعان في $(a,b)$ ويقسمان الحقل إلى أربع مناطق.

يريد اختيار $a$ و$b$ لتكون الأبقار «متوازنة» بصورة معقولة في المناطق الأربع، دون أن تضم منطقة أبقارًا كثيرة جدًا. ليكن $M$ أكبر عدد أبقار في إحدى المناطق الأربع. يريد جعل $M$ أصغر ما يمكن. ساعده في تحديد أصغر قيمة ممكنة له.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $N$. تحتوي الأسطر $N$ التالية على موقع بقرة لكل سطر: إحداثياها $x$ و$y$.

الإخراج

اطبع أصغر قيمة ممكنة لـ $M$ عند وضع السياجين بصورة مثلى.

أمثلة

الإدخال 1

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

الإخراج 1

2

مؤلف المسألة: Brian Dean