MACHINE - Xếp lịch thí nghiệm
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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 si và thời điểm kết thúc ti (si < ti). Vì lý do kỹ thuật nên không có hai giai đoạn nào giao nhau, (hai giai đoạn ij là không giao nhau nếu ti < sj hoặc tj < si). 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 ti − si đơ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 ≤ 106 , k ≤ 3);
• Dòng i + 1:chứa hai số nguyên dương siti (si < ti ≤ 3 × 106 )

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.

Ví dụ

Input

5 2
8 12
6 11
3 9
2 5
1 4

Output

8

Giải thích

Máy sẽ chạy tốt nhất trên hai giai đoạn không giao nhau [2, 5] và [6, 11] và sẽ thu được 8 đơn vị chất B


Nguồn: ĐPT '1819

Back to Top