Một thanh gỗ dài N mét. Có bảng giá bán các đoạn gỗ độ dài 1, 2, ..., N. Hãy cắt thanh gỗ thành các đoạn nhỏ sao cho tổng giá bán thu được là cao nhất.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: N số nguyên là giá bán của đoạn gỗ độ dài 1, 2, ..., N.

Dữ liệu ra:

Giá trị lớn nhất thu được.

Ràng buộc:

1 <= N <= 100

Ví dụ:

Input:

4 
1 5 8 9

Output:

10

Giải thích: Cắt thành 2 đoạn độ dài 2 (giá 5+5=10).