#160. Con Ếch 2 (FROG2)

Có tảng đá, được đánh số . Với mỗi (), tảng đá có chiều cao là . Một con ếch ban đầu ở tảng đá . Nó sẽ lặp lại hành động sau một số lần để đến được tảng đá : Nếu con ếch hiện đang ở trên đá , nó có thể nhảy đến bất kỳ tảng đá nào trong các đá . Chi phí phát sinh khi nhảy từ đá sang đá là .

Yêu cầu: Tìm tổng chi phí tối thiểu có thể để đến được tảng đá .

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên và .
• Dòng thứ hai chứa số nguyên .

Kết quả: In ra chi phí tối thiểu.

Ví dụ:

Dữ liệu:

5 3
10 30 40 50 20

Kết quả:

30

Giải thích: Một đường đi tối ưu là .

• Chi phí từ là .
• Chi phí từ là . Tổng chi phí là .

Giới hạn: