Chúng ta đều biết, mỗi người khi tiêm Vaccine phòng Covid đều phải thực hiện hai bước: khám sàng lọc và tiêm, việc khám sàng lọc phải thực hiện trước.

Tại một cơ sở tiêm Vaccine phòng Covid đã có n người đến chờ tiêm, người thứ i sẽ mất thời gian a_i để khám sàng lọc và mất thời gian b_i để tiêm.

Cơ sở này chỉ có đúng hai bác sĩ, một bác sĩ chuyên khám sàng lọc và một bác sĩ chuyên tiêm. Tại mỗi thời điểm chỉ có thể khám sàng lọc cho không quá một người, việc khám sàng lọc có thể thực hiện theo thứ tự tùy ý. Tại mỗi thời điểm cũng chỉ có thể tiêm cho không quá một người, việc tiêm cũng có thể thực hiện theo thứ tự tùy ý (trong số những người đã khám sàng lọc).

Giả thiết rằng tất cả n người này đều có thể tiêm Vaccine, việc sắp xếp khám sàng lọc và tiêm được thực hiện tối ưu. Tính thời gian tối thiểu để đơn vị này có thể tiêm xong cho n người.

Dữ liệu vào: Đọc từ tập ANTICOVID.INP gồm:

- Dòng đầu tiên chứa số nguyên dương n(1 ≤ n ≤ 10⁵);

- n dòng sau, dòng thứ i chứa hai số nguyên dương a, b (1 ≤ a_i, b_i ≤ 5.10⁴).

Dữ liệu ra: Ghi ra tệp ANTICOVID.OUT một dòng duy nhất chứa số nguyên dương là thời gian tối thiểu cần thiết để tiêm xong cho n người.