농부 존은 많은 양의 우유로 경제적으로 도움을 주는 소들을 위해 N ( 1 <= N <= 2000) 개의 맛있는 과자를 샀다. 존은 하루에 하나의 과자를 팔아서 주어진 시간 내에 최대의 돈을 벌기를 원한다.

이 과자는 몇가지 흥미로운 것이 있다.

• 과자는 차례대로 1 , 2 , 3 ... N 까지 번호가 부여되었다. 팔수 있는 과자는 양쪽 끝의 과자만이 가능하다.
• 와인과 맛있는 치즈와 같이 과자는 시간이 지날수록 더욱 높은 가치를 가진다.
• 과자는 고르지 않다. 어떤 것은 더욱 좋고 높은 가치를 가진다. 과자 i 는 v(i) ( 1 <= v(i) <= 1000 )의 가치를 가진다. 소들은 오래된 과자를 위해서 더 많은 돈을 지불해야 한다. 소들은 v(i) * a 에 대한 돈을 지불해야 한다. a 는 과자의 경과시간이다.

첫 번째 과자는 경과시간 1 로 팔고 , 다음 날 부터 경과시간이 1 씩 증가한다.

입력

출력

입출력 예

입력

5
1
3
1
5
2

출력

43

보충 설명

5 개의 과자 첫 날 1 번 과자( v(1) = 1 ) 혹은 5 번 과자( v(5) = 2 )를 팔수 있다.

i	1	2	3	4	5
v(i)	1	3	1	5	2
판 순서	1	3	4	5	2

최대값= 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43

출처:USACO 2006 February Gold & Silver