시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 476 167 137 37.845%

## 문제

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.

## 입력

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.

## 출력

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

## 예제 입력 1

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


## 예제 출력 1

2


## 출처

• 데이터를 추가한 사람: rdd6584