Hai cô em họ của Bessie là Ella và Bella đang đến thăm trang trại. Đáng tiếc, kể từ khi tới đây, chúng chẳng làm gì ngoài việc nghịch ngợm.

Trong trò quậy phá mới nhất, chúng quyết định cắt càng nhiều cỏ càng tốt. Vùng đồng cỏ tốt nhất của trang trại có dạng một hình vuông lớn kích thước \(T \times T\). Góc dưới bên trái là \((0,0)\) và góc trên bên phải là \((T,T)\). Do đó, hình vuông chứa \((T+1)^2\) điểm nguyên (các điểm có tọa độ nguyên).

Ella và Bella dự định cùng bắt đầu tại \((0,0)\) rồi chạy với tốc độ đơn vị đến \((T,T)\), mỗi cô giữ một đầu của một sợi dây rất sắc và có khả năng co giãn rất lớn. Cỏ trong bất kỳ vùng nào mà sợi dây quét qua đều sẽ bị cắt. Ella và Bella có thể đi theo những đường khác nhau, nhưng mỗi đường chỉ gồm các bước đi lên trên và sang phải, từ một điểm nguyên đến một điểm nguyên khác.

Bessie khá lo rằng quá nhiều cỏ sẽ bị cắt, nên cô nghĩ ra một kế hoạch khéo léo để ràng buộc các đường đi của Ella và Bella. Có \(N\) bông hoa ngon lành (\(1 \leq N \leq 2 \cdot 10^5\)) nằm rải rác trên đồng cỏ, mỗi bông ở một điểm nguyên khác nhau. Bessie sẽ chọn một tập \(S\) gồm các bông hoa mà cả Ella và Bella bắt buộc phải ghé thăm (tức là đường đi của Ella phải đi qua tất cả các bông hoa trong \(S\), và đường đi của Bella cũng vậy). Để thêm nhiều điểm trung gian nhất có thể vào các đường đi này, Bessie sẽ chọn \(S\) có kích thước lớn nhất trong số các tập con của các bông hoa mà một con bò di chuyển lên trên và sang phải từ \((0,0)\) đến \((T,T)\) có thể ghé thăm.

Ella và Bella sẽ cố gắng tối đa hóa lượng cỏ chúng cắt, với ràng buộc phải ghé thăm các bông hoa trong \(S\). Hãy giúp Bessie chọn \(S\) sao cho lượng cỏ bị cắt nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\) (\(1 \leq T \leq 10^6\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ nguyên \((x_i, y_i)\) của một bông hoa. Dữ liệu bảo đảm \(1 \leq x_i, y_i \leq T-1\) với mọi \(i\), và không có hai bông hoa nào nằm trên cùng một đường ngang hoặc đường dọc.

Phân nhóm

Trong ít nhất 20% số test, dữ liệu còn bảo đảm \(N \leq 3200\).

Dữ liệu ra

In ra một số nguyên duy nhất là lượng cỏ bị cắt nhỏ nhất có thể.

Ví dụ

5 20
19 1
2 6
9 15
10 3
13 11

117

Nguồn

USACO 2019 February Contest, Platinum — Mowing Mischief

Tác giả: Dhruv Rohatgi.