Hiếu có các chú dê đứng ở vị trí riêng biệt \((x_1,y_1)...(x_n,y_n)\) trên cánh đồng hai chiều của anh ấy \((1≤N≤100\), và các giá trị \(x_i\) và \(y_i\) là các số nguyên lẻ dương không vượt quá \(B)\). Hiếu muốn phân chia cánh đồng của mình bằng cách xây một hàng rào dài (có chiều dài vô hạn) theo hướng bắc-nam với phương trình \(x=a\) (\(a\) sẽ là một số nguyên chẵn, do đó đảm bảo rằng anh ấy không xây hàng rào qua vị trí của bất kỳ chú dê nào). Anh ấy cũng muốn xây một hàng rào dài (có chiều dài vô hạn) theo hướng đông-tây với phương trình \(y=b\), nơi \(b\) là một số nguyên chẵn. Hai hàng rào này gặp nhau tại điểm \((a,b)\), và cùng nhau chúng chia cánh đồng thành bốn khu vực.

Hiếu muốn chọn \(a\) và \(b\) sao cho số lượng chú dê xuất hiện trong bốn khu vực tạo thành được "cân bằng" một cách hợp lý, không có khu vực nào chứa quá nhiều chú dê. Gọi \(M\) là số lượng chú dê tối đa xuất hiện trong một trong bốn khu vực, Hiếu muốn làm cho \(M\) nhỏ nhất có thể. Hãy giúp anh ấy xác định giá trị nhỏ nhất có thể của \(M\).

Đối với năm trường hợp thử đầu tiên, \(B\) được đảm bảo là tối đa \(100\). Trong tất cả các trường hợp, \(B\) được đảm bảo là tối đa \(1,000,000\).

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa hai số nguyên, \(N\) và \(B\).
\(N\) dòng tiếp theo mỗi dòng chứa vị trí của một chú dê, chỉ ra tọa độ \(x\) và \(y\) của nó.

OUTPUT FORMAT

Ví dụ:

Input

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

Output

2

Giải thích ví dụ mẫu:

• Ví dụ 1:
  • Bằng cách chọn các hàng rào tại x=5 và y=5, số lượng chú dê tối đa trong bất kỳ khu vực nào là 2.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House