An Vũ: PTIT Code

C04035 - Leo núi

Có N (1≤N≤25000) người leo lên và leo xuống trên 1 ngọn núi. Người i mất U(i) thời gian leo lên và D(i) thời gian để leo xuống. Trong một thời điểm chỉ có tối đa người 1 người có thể lên và tối đa 1 người có thể xuống (có thể 1 người lên, 1 người xuống). Những người khác có thể đứng chờ ở đỉnh ngọn núi. Thứ tự đi xuống có thể khác thứ tự đi lên. Bạn hãy xác định xem thời gian tối thiểu để cho N người lên và xuống ngọn núi là bao nhiêu.

Input: Dòng 1 ghi số N. N dòng tiếp theo chứa 2 số U(i) và D(i) (1 ≤ U(i) , D(i) ≤ 50000)

Output: Ghi ra thời gian tối thiểu có thể.

Ví dụ: (Giải thích: đi lên và xuống theo thứ tự người 3->1->2)

Input

Output

6 4

8 1

2 3

[PTIT Code] [Ngôn ngữ lập trình C++ - INT1339] Danh sách bài tập và bài làm mẫu

[PTIT Code] [Tin học cơ sở 2 - C - INT1155] Danh sách bài tập và bài làm mẫu

[PTIT Code] C04035 - Leo núi - Lập lịch tối ưu cho hai công đoạn bằng nguyên tắc Johnson

C04035 - Leo núi