Leo Núi

Có $N$ người cần vượt qua một ngọn núi. Người thứ $i$ cần $U_i$ thời gian leo lên và $D_i$ thời gian leo xuống. Tại mỗi thời điểm, chỉ có tối đa 1 người đang leo lên và tối đa 1 người đang leo xuống. Có thể chờ trên đỉnh và leo xuống theo thứ tự khác.

Hãy tìm thời gian tối thiểu để tất cả hoàn thành.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Hai số nguyên $U_i$ và $D_i$

Dữ liệu ra

• In ra thời gian tối thiểu.

Ràng buộc

• $1\le N\le 25000$
• $1\le U_i,D_i\le 50000$

Ví dụ