FJ mua $N$ $(1 \le N \le 2000)$ món ngon cho bò kiếm tiền bằng nhiều sữa. Mỗi ngày bán một, tối đa thu nhập một khoảng thời gian.

Chúng thú vị:

• Đánh số $1..N$, theo thứ tự một hàng trong hộp dài mở hai đầu. Mỗi ngày có thể lấy một từ bất kỳ đầu.
• Như rượu ngon và phô mai ngon, càng lâu càng tốt và đắt.
• Không đều, có món tốt và giá trị nội tại cao hơn. Món $i$ có giá trị $v(i)$ ($1 \le v(i) \le 1000$).
• Bò trả cao hơn cho cũ: tuổi $a$ trả $v(i)*a$.

Cho giá trị $v(i)$ theo chỉ số $i$ trong hộp, tối đa thu bao nhiêu khi thứ tự bán tối ưu?

Bán đầu ngày 1 với tuổi $a=1$, mỗi ngày sau tăng tuổi 1.

Dữ liệu vào

• Dòng 1: một số nguyên $N$.
• Dòng $2..N+1$: dòng $i+1$ giá trị $v(i)$.

Dữ liệu ra

• Dòng 1: thu nhập bán tối đa.

Ví dụ

Dữ liệu vào 1

5
1
3
1
5
2

Dữ liệu ra 1

43

Ghi chú

Bán giá trị $1, 3, 1, 5, 2$ theo chỉ số $1, 5, 2, 3, 4$, thu $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Tác giả: Marco Gallotta (2005).