Tại trang trại của Duy có \(N\) con chó dữ, trong một ngày mưa, tất cả đàn chó dữ đã xổng chuồng và xông ra phá hoại vườn hoa xinh đẹp của Duy. Mỗi con chó có đặc điểm sau:

Di chuyển từ vườn hoa về chuồng mất \(t(s)\);

Sau 1s sẽ phát nát \(d\) bông hoa.

Duy trong một lần, chỉ có thể dắt một con chó về chuồng, nếu dắt con chó nào về chuồng tổng thời gian di chuyển là \(2*t(s)\) (dắt chó về và di chuyển quay lại vườn hoa, \(t\): là thời gian di chuyển của cua chó đó).

Yêu cầu: Bạn hãy tính xem, ít nhất bao nhiêu bông hoa bị phá nát?

Dữ liệu vào:

Dòng đầu chứa số nguyên dương \(N (1<=N<=100000)\)

\(N\) dòng sau, dòng thứ gồm hai số t và d tương ứng với đặc điểm của con chó \(i. (1<=t<=2*1000000; 1<=d<=100)\)

Dữ liệu ra:

Một số duy nhất là số bông hoa ít nhất bị phá hủy.

Sample Input

6
3 1
2 5
2 3
3 2
4 1
1 6

Sample Output

86

Giải thích:

Dắt chó theo thứ tự: 6 , 2, 3, 4, 1, 5