Mỗi học sinh \(i\) ở trường trong khoảng thời gian nửa kín từ mili giây \(l_i\) đến trước \(r_i\). Một lớp phụ đạo cần có ít nhất \(k\) học sinh, và mọi học sinh tham gia phải ở trường trong toàn bộ thời gian của lớp. Hãy tìm thời lượng lớn nhất có thể tổ chức, hoặc \(0\) nếu không thể tổ chức lớp.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le n,k\le3\cdot10^5\)). \(n\) dòng tiếp theo chứa \(l_i,r_i\) (\(1\le l_i<r_i\le86\,400\,000\)).

Dữ liệu ra

In thời lượng lớn nhất có thể tổ chức lớp phụ đạo, hoặc 0.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(13\) điểm: \(k=1\).
2. \(27\) điểm: \(n\le1000\), \(k=2\).
3. \(11\) điểm: \(r_i\le100\).
4. \(19\) điểm: không có ràng buộc thêm.

Ví dụ

5 1
1 3
1 4
1 5
1 6
1 7

6

5 2
6 10
8 14
5 9
5 6
4 6

3

Nguồn

COCI 2025/2026 - Vòng 2, bài Dodatna.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.