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

Có $N$ nhân viên cứu hộ, nhân viên thứ $i$ được phân công một ca trực liên tục biểu diễn bởi đoạn thời gian $[l_i,r_i]$. Quản lý buộc phải sa thải đúng $K$ nhân viên trong số $N$ nhân viên này.

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

Các ca trực có thể chồng lấp nhau tùy ý.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên $N$ và $K$.
• $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$.
• Các ca trực được cho theo thứ tự bất kỳ.

Dữ liệu ra

Một số nguyên duy nhất: tổng thời gian được bao phủ lớn nhất sau khi sa thải đúng $K$ nhân viên.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le K\le min(N,100)$
• $0\le l_i<r_i\le {10}^9$
• Tất cả $2N$ giá trị $l_i,r_i$ đều đôi một phân biệt.

Ví dụ