\(N\) con bò của Farmer John đang đứng tại các vị trí phân biệt \((x_1,y_1) \ldots (x_n,y_n)\) trên trang trại hai chiều của ông (\(1 \leq N \leq 1000\); các \(x_i\) và \(y_i\) là những số nguyên dương lẻ không vượt quá \(1\,000\,000\)). FJ muốn chia cánh đồng bằng cách dựng một hàng rào dài theo hướng bắc–nam (trên thực tế có thể xem là dài vô hạn) với phương trình \(x=a\). \(a\) là một số nguyên chẵn, nhờ đó ông chắc chắn không dựng hàng rào xuyên qua vị trí của bất kỳ con bò nào. Ông cũng muốn dựng một hàng rào dài theo hướng đông–tây (trên thực tế có thể xem là dài vô hạn) với phương trình \(y=b\), trong đó \(b\) là một số nguyên chẵn. Hai hàng rào cắt nhau tại điểm \((a,b)\) và cùng chia cánh đồng thành bốn vùng.

FJ muốn chọn \(a\) và \(b\) sao cho số bò trong bốn vùng tạo thành tương đối "cân bằng", không có vùng nào chứa quá nhiều bò. Gọi \(M\) là số bò lớn nhất trong một trong bốn vùng, FJ muốn làm cho \(M\) nhỏ nhất có thể. Hãy giúp ông xác định giá trị nhỏ nhất có thể của \(M\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ \(x\) và \(y\) của một con bò.

Dữ liệu ra

In giá trị nhỏ nhất có thể của \(M\) mà FJ đạt được khi đặt các hàng rào một cách tối ưu.

Ví dụ

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

2

Nguồn

USACO 2016 February Contest, Silver - Load Balancing: https://usaco.org/index.php?page=viewproblem2&cpid=619

Tác giả: Brian Dean.