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\ldots 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: Từ tệp văn bản TIENPHAT.INP:

• Dòng đầu tiên chứa số nguyên \(n\ (1 \leq n \leq 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}\ (\left| x_{i} \right| \leq 10^{9};0 \leq c_{i} \leq 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ả: Đưa ra tệp văn bản TIENPHAT.OUT chỉ gồm một số nguyên duy nhất là tổng tiền phạt ít nhất phải đóng.

Ví dụ:

Giải thích:

Ví dụ 1: Lập chốt chặn tại điểm có tọa độ \(x = 1\).

Ví dụ 2: Lập chốt chặn tại điểm có tọa độ \(x = 1\) và \(x = 5\).

Ràng buộc:

+ Có 40% số test tương ứng 40% số điểm có \(1\ \leq \ n\ \leq \ 20\);

+ Có 60% số test còn lại tương ứng 60% số điểm có \(20\ < \ n\ \leq \ 3000\).