Một kỹ sư cần lập lịch cho một máy chạy trên một số giai đoạn nằm trong n thời điểm 1, . . . , n để làm thí nghiệm sản xuất ra chất B. Mỗi giai đoạn i được cho bởi thời điểm bắt đầu s_i và thời điểm kết thúc t_i (s_i < t_i). Vì lý do kỹ thuật nên không có hai giai đoạn nào giao nhau, (hai giai đoạn i và j là không giao nhau nếu t_i < s_j hoặc t_j < s_i). Nếu thí nghiệm chạy vào giai đoạn i thì lượng chất B được sản xuất ra sẽ bằng t_i − s_i đơn vị.

Yêu cầu: Hãy giúp anh kỹ sư chọn được k (k ≤ 3) giai đoạn không giao nhau sao cho tổng lượng chất B sản xuất được là lớn nhất.

Dữ liệu vào

• Dòng 1: chứa hai số nguyên dương n k (2 ≤ n ≤ 10⁶ , k ≤ 3);
• Dòng i + 1:chứa hai số nguyên dương s_i và t_i (s_i < t_i ≤ 3 × 10⁶ )

Kết quả

Ghi ra duy nhất một số nguyên là lượng chất B thu được. Ghi ra -1 nếu không có phương án chọn.