FJ
muốn bán N miếng bánh làm từ sữa các con bò. (1≤N≤2000). FJ bãn mỗi ngày một miếng
bánh và muốn nhận được số tiền lớn nhất từ việc bán những cái bánh đó trong một
khoảng thời gian có hạn. Mỗi miếng bánh có giá trị cao nhờ nhiều nguyên nhân:
+
các miếng bánh được xếp trong một băng dài được đánh số từ 1 đến N. Mỗi ngày FJ
có thể lấy 1 miếng bánh ở đầu này hoặc đầu kia của băng đó.
+
Cũng giống như rượu và pho-mat, các miếng
bánh có tuổi thọ càng cao thì càng có giá trị.
+
Giá trị của miếng bánh cũng không cố định. Miếng bánh thứ i có giá trị Vi
(1≤Vi≤1000) nếu như miếng bánh đó được bán vào ngày 1.
+ Mỗi
chiếc bánh có giá trị phụ thuộc vào tuổi của nó. Mỗi miếng bánh sẽ nhận được
a*Vi giá trị với chiếc bánh thứ i có a tuổi.
Yêu cầu: Cho
các giá trị Vi. Hãy tìm giá trị lớn nhất Fj có thể nhận được từ việc
bán những chiếc bánh.
Chiếc
bánh đầu tiên có tuổi là 1, các miếng bánh được bán sau sẽ có tuổi nhiều hơn miếng
bánh bán trước là 1.
Dữ liệu vào:
+ Dòng đầu tiên là số nguyên dương N
+ N dòng sau, dòng thứ i là số nguyên Vi
Dữ liệu ra: Một số nguyên duy nhất là giá trị lớn nhất mà FJ thu được
Ví dụ:
INPUT
|
OUTPUT
|
5
1
3
1
5
2
|
43
|
