MACHINE01 - 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 chọn ra 2 giai đoạn trong số N giai đoạn cho trước để làm thí nghiệm sản xuất ra chất C. Mỗi giai đoạn i, 1 ≤ i ≤ n đượ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 hai giai đoạn được chọn không được phép 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 C đượ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 hai giai đoạn không giao nhau sao cho tổng lượng chất C sản xuất được là lớn nhất.

Dữ liệu vào

• Dòng 1: chứa một số nguyên n (2 ≤ n ≤ 106)
• 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 C thu được. Ghi ra -1 nếu không chọn được hai giai đoạn nào không giao nhau

Ví dụ

Input

5
8 12
6 11
3 9
2 5
1 4

Output

8

Giải thích Hai giai đoạn lớn nhất không giao nhau là [2, 5] và [6, 11] sẽ thu được 8 đơn vị chất C.


Nguồn: ĐPT '1819

Back to Top