USACO

USACO 2016 February Contest, Bronze

Problem 3. Load Balancing

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John's

$N$ cows are each standing at distinct locations

$(x_1, y_1) \ldots (x_n, y_n)$ on his two-dimensional farm (

$1 \leq N \leq 100$ , and the

$x_i$ 's and

$y_i$ '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 (file balancing.in):

The first line of the input contains two integers,

$N$ and

$B$ . The next

$n$ lines each contain the location of a single cow, specifying its

$x$ and

$y$ coordinates.

OUTPUT FORMAT (file balancing.out):

You should output the smallest possible value of

$M$ that FJ can achieve by positioning his fences optimally.

SAMPLE INPUT:

SAMPLE OUTPUT:

Problem credits: Brian Dean

Contest has ended. No further submissions allowed.