13002번 - Happy Cow

천나라에 살고있는 민호는 애지중지하는 소 한마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다.

민호는 여물을 관리하기 쉽게 폭은 좁지만 너비가 매우 긴 창고에 차례대로 넣었고, 왼쪽부터 한개씩 1번, 2번, 3번, ... , N번 여물이라 부르기로 했다. 각각의 여물들은 소가 먹었을 때 느끼는 행복이 다를수가 있다. 예를 들어 1번 여물을 먹으면 소가 느끼는 행복은 20이지만 2번 여물을 먹으면 소가 느끼는 행복은 10일수가 있다는 것이다. 이를 편의상 행복도라 부르기로 하자.

그리고 여물들은 날이 지날수로 숙성이 되어 맛이 더 좋아져 행복도가 올라간다. 이는 (행복도 * 여물을 구매한 뒤 지난 날자)로 계산할 수 있다. 여물을 구매한 뒤 지난 날자는 구매한 당일의 날이 1이고 그 다음날이 2라고 계산한다.

이것들을 백만년 숙성시킨 뒤 소에게 주면 소는 극락을 맛보겠지만 그때까지 기다릴 수 없던 민호는 여물을 구매한 날부터 N번째 날까지, 하루에 한 개의 여물을 소에게 주기로 하였다. 하지만 폭이 좁고 너비가 매우 긴 창고에 여물을 저장했기 때문에 중간에 있는 여물을 꺼내는건 불가능 하고 왼쪽과 오른쪽, 양쪽 끝에서 하나만 꺼내 소에게 주는 것이 가능하다. 즉 i ≤ j (1 ≤ i ≤ j ≤ N) 의 여물이 남아 있다면 민호는 i번 여물이나 j번 여물을 선택을 해서 소에게 줘야 한다는 뜻이다. i또는 j외의 여물을 소에게 줄 수 없다.

민호는 소가 최대로 높은 행복을 느꼇으면 좋겠다고 생각 한다. N일에 걸쳐 모든 여물을 소에게 줬을 때 소가 느끼는 행복도의 합이 최대가 되는 경우를 구해주자.

첫 번째 줄에 여물의 개수 N (1 ≤ N ≤ 2000) 이 주어진다.

두 번째 줄에 여물의 행복도 H_i (1 ≤ H_i ≤ 1000, 1 ≤ i ≤ N) 이 공백을 구분으로 N개 주어진다.

N일에 걸쳐 모든 여물을 소에게 줬을 때 소가 느낄 수 있는 행복도들의 합중 최대를 출력한다.