G. DPHALL – Xếp lịch hội trường

Hội trường trường THPT Chuyên Sơn La vừa khánh thành đã có rất nhiều tập thể lớp muốn xin sử dụng hội trường để tổ chức các chương trình.

Có yêu cầu sử dụng hội trường, mỗi một yêu cầu sử dụng hội trường có dạng một cặp số nguyên không âm là thời gian bắt đầu và thời gian kết thúc sử dụng hội trường. Do có nhiều yêu cầu mà tại mỗi thời điểm nhà trường có thể đáp ứng được một yêu cầu, hãy giúp nhà trường tính toán chọn danh sách các yêu cầu cho phép sử dụng hội trường sao cho tổng thời gian phục vụ được nhiều nhất (mỗi yêu cầu được chấp nhận sẽ được phép sử dụng hội trường từ thời điểm bắt đầu đến thời điểm kết thúc của yêu cầu đó).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương là thời điểm bắt đầu và kết thúc của yêu cầu thứ .

Dữ liệu ra:

• Một số nguyên duy nhất là tổng thời gian sử dụng hội trường tối đa có thể được.

Ví dụ:

Dữ liệu vào:

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Dữ liệu ra:

16

Giới hạn:

• .