頁面無法載入？點擊這裡可能會修復。
Placeholder

#3973

Load Balancing 2s 512MB

問題

농부 존의 N 마리 소들이 각각 그의 2차원 농장의 서로 다른 위치 (x_1, y_1) ... (x_n, y_n)에 서 있습니다 (1 ≤ N ≤ 100, 그리고 x_i와 y_i는 최대 B 크기의 양의 홀수 정수입니다).

존은 x = a라는 방정식을 가진 북남 방향의 긴(사실상 무한 길이의) 울타리를 세워 그의 농장을 나누고 싶어합니다.

그는 또한 y = b라는 방정식을 가진 동서 방향의 긴(사실상 무한 길이의) 울타리를 세우고 싶어합니다. 이 두 울타리는 (a, b) 지점에서 교차하며, 함께 그의 농장을 네 구역으로 나눕니다.

(a와 b는 짝수 정수로, 어떤 소의 위치를 가로지르지 않도록 보장합니다)

존은 결과적으로 나오는 네 구역에 있는 소들의 수가 너무 많이 차이나지 않도록 "균형 잡히게" 만들고 싶어합니다.

네 구역 중 한 구역에 속하는 소들의 최대 수를 M이라고 할 때, 존은 이 M 값을 가능한 한 작게 만들고 싶어합니다. 이 최소 M 값을 결정하는 것을 도와주세요.

B는 최대 1,000,000임이 보장됩니다.


輸入

첫 번째 줄에는 두 정수 N과 B가 주어집니다.

다음 N 줄에는 각각 하나의 소의 위치를 나타내는 x와 y 좌표가 주어집니다.


輸出

존이 울타리를 최적으로 배치하여 달성할 수 있는 가장 작은 M 값을 출력하세요.


範例 

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


來源

USACO 2016 February Bronze

需要登入才能撰寫程式碼。