Bạn cần thực thi càng nhanh càng tốt N chương trình máy tính đánh số 1, 2,...,N. Chương trình số hiệu i mất S[i] đơn vị thời gian cài đặt và R[i] đơn vị thời gian chạy. Chiếc IPHONE 13 của bạn được trang bị bộ xử lí lõi tứ mạnh mẽ nhất hiện nay cho phép thực hiện nhiều công việc cũng như chạy nhiều chương trình cùng một lúc mà không hề chậm đi. Tuy nhiên việc cài đặt một chương trình đòi hỏi sự tập trung chú ý cao nên bạn không thể tiến hành cài đặt hai chương trình trong cùng thời điểm. Khi một chương trình được cài xong, nó sẽ tự động chạy ngay lập tức và bạn có thể chuyển sang cài chương trình khác, thời gian chuyển coi như không đáng kể.

Hãy xác định xem bạn có thể chạy xong cả chương trình trong tổng thời gian ngắn nhất là bao nhiêu.

Dữ liệu

• Dòng ghi N (0<=N<=100).

• Dòng thứ trong dòng tiếp theo ghi hai số nguyên S[i], R[i] trong phạm vi [1...1000]

Kết quả

• Chỉ gồm dòng ghi tổng thời gian ngắn nhất tìm được

Sample Input

4
4 2
2 2
1 2
3 4

Sample Output

12