$N$ הפרות של Farmer John עומדות במיקומים שונים $(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)$ ומחלקות את השדה לארבעה אזורים.

FJ רוצה לבחור $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