Người thầy nổi tiếng Jakov rất thích dạy học và giúp đỡ các học sinh chăm chỉ. Trong năm học này, thầy quyết định mở thêm một lớp tin học phụ đạo cho một nhóm học sinh có những yêu cầu rất kỳ lạ. Tuy nhiên, điều kiện để lớp phụ đạo được mở thì đơn giản hơn nhiều:

• Mọi học sinh tham gia lớp phụ đạo phải có mặt ở trường trong suốt toàn bộ thời gian lớp học diễn ra.
• Lớp phụ đạo chỉ được tổ chức nếu có ít nhất ~k~ học sinh tham gia.

Nhờ sự hỗ trợ của hiệu trưởng, Jakov biết được thời gian biểu của cả ~n~ học sinh. Với mỗi học sinh ~i~, thầy biết rằng em đó có mặt ở trường từ thời điểm ~l_i~ cho tới trước thời điểm ~r_i~.

Hãy giúp Jakov trả lời câu hỏi: thời lượng lớn nhất của lớp phụ đạo mà thầy có thể tổ chức là bao nhiêu? Nếu hoàn toàn không thể mở lớp, hãy in ra ~0~.

Lưu ý: thời điểm đầu tiên mà học sinh ~i~ có mặt ở trường là ~l_i~, còn thời điểm cuối cùng là ~r_i - 1~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~, với ~1 \le n, k \le 3 \cdot 10^5~.

~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i~ và ~r_i~, với ~1 \le l_i < r_i \le 86\,400\,000~.

Output

In ra trên dòng duy nhất một số nguyên: thời lượng lớn nhất của lớp phụ đạo mà Jakov có thể tổ chức, hoặc ~0~ nếu không thể tổ chức.

Chấm điểm

• Subtask ~1~ (~13~ điểm): ~k = 1~
• Subtask ~2~ (~27~ điểm): ~1 \le n \le 1000~, ~k = 2~
• Subtask ~3~ (~11~ điểm): ~r_i \le 100~
• Subtask ~4~ (~19~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

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

Sample Output ~1~

6

Sample Input ~2~

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

Sample Output ~2~

3

Giải thích

• Ví dụ ~2~: Thời lượng dài nhất của lớp phụ đạo là ~3~, vì học sinh ~1~ và học sinh ~3~ cùng có mặt trong trường tại các thời điểm ~6~, ~7~, và ~8~.