Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P151PROB - ROUND 1B - Rubik đi siêu thị

Rubik đi siêu thị mua n món đồ và để vào trong xe đẩy rồi mang ra quầy thanh toán. Biết mặt hàng thứ i có giá là C_i và người thu ngân cần thời gian T_i để có thể xác nhận mặt hàng này. Nhưng Rubik là thánh ăn trộm nên anh ta đã sắp xếp thứ tự các mặt hàng cho người thu ngân xác nhận theo ý của mình, khi người thu ngân bận làm thủ tục là Rubik sẽ có thể ăn trộm 1 món đồ từ chính xe của mình và mất 1 giây.

Bạn hãy tính xem số tiền tối thiểu mà Rubik phải trả là bao nhiêu?

Input

Dòng đầu tiên chứa số mặt hàng n ( 1 <= n <= 2000).

Sau đó n dòng là cặp T_i và C_i tương ứng là thời gian xác nhận và giá tiền của mặt hàng thứ i (0 <= T_i <= 2000, 1 <= C_i <= 10^9 ). Nếu T_i bằng 0 thì Rubik không thể trộm thứ gì khi nhân viên xác nhận mặt hàng thứ i.

Output

Dòng duy nhất chứa số tiền ít nhất mà Rubik phải trả.

Example

Input:

4

2 10

0 20

1 5

1 3 Output: 8

Được gửi lên bởi:adm
Ngày:2015-03-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2015-05-04 06:39:48 Hiệp
Gọi F là kết quả với F[i] là giá trị nhỏ nhất khi mua được i món hàng.

Khi nhập món hàng thứ i thì ta có 2 khả năng:

– Chọn món hàng thứ i nhân viên thu ngân kiểm tra, sẽ mất t_i giây và lúc đó sẽ ăn

trộm thêm được t_i món hàng, cộng với cả món hàng thứ i thì sẽ có i + t_i + 1 món

hàng được lấy bao gồm cả của Rubik và số món hàng để lại thanh toán và ta sẽ có mối

liên hệ giữa f[j + t_i + 1] với f[j] với j bất kì.

– Món hàng thứ i có thể được ăn trộm từ thời gian của các món hàng trước, trường hợp

này đã được xét ở trên với j bất kì.

Kết quả bài toán sẽ là f[n] khi cả n món đều đã được lấy hết.
2015-05-03 08:36:14 Ngát Taro


Last edit: 2015-05-24 15:18:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.