$N$ con bò của Farmer John đứng ở các vị trí khác nhau $(x_1, y_1) \ldots (x_n, y_n)$ trên trang trại hai chiều ($1 \leq N \leq 100,000$, và $x_i$, $y_i$ là số nguyên dương lẻ không quá $1,000,000$). FJ muốn chia đồng bằng hàng rào dài, coi như vô hạn, theo hướng bắc-nam có phương trình $x=a$. $a$ là số nguyên chẵn, bảo đảm không đi qua vị trí bò nào. Anh cũng muốn hàng rào dài, coi như vô hạn, theo hướng đông-tây $y=b$, với $b$ nguyên chẵn. Hai hàng rào cắt tại $(a,b)$, chia đồng thành bốn vùng.

FJ muốn chọn $a$ và $b$ để số bò ở bốn vùng tương đối «cân bằng», không vùng nào quá nhiều bò. Gọi $M$ là số bò lớn nhất trong một vùng. Anh muốn $M$ nhỏ nhất có thể. Hãy giúp tìm giá trị nhỏ nhất đó.

Dữ liệu vào

Dòng đầu chứa một số nguyên $N$. $N$ dòng tiếp theo cho vị trí một con bò mỗi dòng: tọa độ $x$ và $y$.

Dữ liệu ra

In giá trị $M$ nhỏ nhất đạt được bằng cách đặt hàng rào tối ưu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2

Tác giả bài toán: Brian Dean