Cho một cây gỗ dài n và một dãy các giá bán các đoạn gỗ có độ dài nhỏ hơn n. Xác định giá trị tối đa có thể đạt được bằng cách cắt cây gỗ trên thành các đoạn và bán chúng. Ví dụ, nếu chiều dài của cây gỗ là 8 và giá bán các đoạn gỗ khác nhau được cho như dưới đây, thì có thể đạt được giá trị tối đa là 22 (bằng cách cắt cây gỗ thành hai đoạn dài 2 và 6)
|
Length |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Price |
1 |
5 |
8 |
9 |
10 |
17 |
17 |
20 |
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên dương N, là độ dài cây gỗ.
- N dòng sau, dòng thứ i chứa số nguyên Ci là giá bán bán đoạn gỗ độ dài i.
Kết quả ra: In ra tổng giá trị lớn nhất khi bán cây gỗ.