banner

Bài tập: Load Balancing

Đề bài
Mã bài: Balancing
Kiểu chấm: OI
Dữ liệu nhập: Nhập chuẩn
Kết quả xuất: Xuất chuẩn
Giới hạn thời gian: 1 giây
Được tạo bởi: Trần Đức Doanh
Nội dung:

Farmer John's N cows are each standing at distinct locations (x1,y1)(xn,yn) on his two-dimensional farm (1N100, and the xi's and yi's are positive odd integers of size at most B). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=a (a will be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y=b, where b is an even integer. These two fences cross at the point (a,b), and together they partition his field into four regions.

FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting M be the maximum number of cows appearing in one of the four regions, FJ wants to make M as small as possible. Please help him determine this smallest possible value for M.

For the first five test cases, B is guaranteed to be at most 100. In all test cases, B is guaranteed to be at most 1,000,000.

INPUT FORMAT:

The first line of the input contains two integers, Nand B. The next n lines each contain the location of a single cow, specifying its x and y
coordinates.

OUTPUT FORMAT:

You should output the smallest possible value of M that FJ can achieve by positioning his fences optimally.

SAMPLE INPUT:

7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1

SAMPLE OUTPUT:

2

Xem hướng dẫn cách làm bài
Để làm bài thì bạn cần phải đăng nhập