Trên một đường thẳng song song với trục ~ Ox ~ có ~ n ~ viên bi, viên thứ ~ i ~ ~ ( i = 1…n ) ~ có tọa độ ~ x_i ~. Bạn có thể lập một chốt chặn ngay tại vị trí của một viên bi để ngăn viên bi đó không bị lăn sang trái. Sau khi bạn chọn một số vị trí để lập chốt chặn, các viên bi sẽ được tác động một lực để lăn sang trái theo quy tắc: Nếu gặp chốt chặn thì viên bi sẽ dừng lại và được lấy ra ngoài, ngược lại nếu không gặp bất cứ chốt chặn nào thì nó sẽ lăn mãi.

Với viên bi thứ ~ i ~, nếu bạn lập chốt chặn tại ~ x_i ~ thì bạn phải đóng tiền phạt là ~ c_i ~, nếu để viên bi đó lăn đi thì số tiền bạn phải đóng là quãng đường mà viên bi đó lăn được cho đến khi gặp chốt chặn. Nếu viên bi không gặp bất kì chốt chặn nào thì bạn phải đóng số tiền phạt vô cùng lớn.

Yêu cầu: Hãy cho biết tổng số tiền phạt phải đóng ít nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~ n ~ ~ ( 1 ≤ n ≤ 3000) ~ là số lượng viên bi;
• ~ n ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ x_i ~ và ~ c_i ~ ~ ( | x_i |≤1 0^9; 0 ≤ c_i ≤ 10^9) ~ lần lượt là tọa độ và chi phí lập chốt chặn tại vị trí viên bi thứ ~ i ~. Dữ liệu đảm bảo không có hai viên bi nằm cùng một vị trí.

Kết quả

Một số nguyên duy nhất là tổng tiền phạt ít nhất phải đóng.

Ràng buộc

• Có 40% số test có ~ 1 ≤ n ≤ 20 ~;
• Có 60% số test có ~ 20 < n ≤ 3000 ~.

Ví dụ:

Input 1

3
2 3
1 2
3 4 

Output 1

5 

Input 2

5
7 20
5 8
11 80
1 3
10 45 

Output 2

24