Nhân viên cứu hộ (Platinum)

Có $N$ nhân viên cứu hộ, mỗi người được phân công một ca trực liên tục được biểu diễn bởi đoạn thời gian $[l_i,r_i]$ (với $0\le l_i<r_i\le {10}^9$). Quản lý cần sa thải đúng $K$ nhân viên trong số $N$ nhân viên này.

Hãy tính tổng thời gian bao phủ tối đa có thể đạt được sau khi sa thải đúng $K$ nhân viên. Tổng thời gian bao phủ là độ dài của hợp các đoạn thời gian còn lại.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên $N$ và $K$ ($1\le K\le N\le {10}^5$).
• $N$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $l_i$ và $r_i$ biểu diễn ca trực của nhân viên thứ $i$.
• Tất cả các giá trị $l_i,r_i$ đều phân biệt.

Dữ liệu ra

Một số nguyên duy nhất — tổng thời gian bao phủ tối đa sau khi sa thải đúng $K$ nhân viên.

Ràng buộc

• $1\le K\le N\le {10}^5$
• $0\le l_i<r_i\le {10}^9$

Ví dụ

Ghi chú

• Nếu $K=N$, tất cả nhân viên đều bị sa thải và tổng bao phủ bằng 0.
• Có thể có các đoạn thời gian chồng lấp nhau.