Trong một cuộc thi tìm người thông thái đất nước, Tí được cho N hình trụ đứng với nhiều kích thước khác nhau và yêu cầu phải xếp được toà tháp cao nhất từ các hình trụ theo dúng thứ tự từ 1 đến N sao cho khối ở trên phải được xếp khít với khối ở dưới, hay đường kính đáy của hình trên không vượt quá đường kính đáy hình dưới. Một khối trụ có thể dùng hoặc không dùng nhưng phải theo thứ tự đã cho. Hãy giúp Tí giải bài toán này nhé các bạn.

Dữ liệu: vào từ file TOWER.INP

• dòng đầu ghi số nguyên dương N ( N <= \(10^5\) )
• N dòng tiếp theo mỗi dòng ghi số Ri và Hi là bán kính đáy và chiều cao hình trụ thứ i ( 1 <= Ri <= 500, 1 <= Hi <= 500).

Kết quả: Một số nguyên lớn nhất là chiều cao của toà tháp xếp được.

SAMPLE INPUT:

4
4 2
2 5
1 3 
3 1

SAMPLE OUPUT:

10