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 6 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ể.

Yêu cầu: 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 vào

• 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.

Ví dụ:

Input

4
4 2
2 2
1 2
3 4

Output

12

• Có 30% số test ứng với 30% số điểm của bài có \(1<n<=30;\)
• Có 30% số test ứng với 30% số điểm của bài có \(30<n<=60;\)
• Có 40% số test ứng với 40% số điểm của bài có \(60<n<=100.\)