23032번 - 서프라이즈~

쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다.

컴퓨터정보공학부에는 N명의 학생이 있는데, 학생들은 1부터 N까지 고유한 학번이 부여되어있다. 쿠기는 N명의 학생을 대상으로 스테이크 몇 그램을 먹고 싶은지 설문 조사를 했다. 설문 조사를 마치고 학생들의 설문 결과를 본 쿠기는 경악했다. 이 설문 조사 결과를 기반으로 간식 행사를 진행한다면 다시는 간식 행사를 할 수 없다. 이미 간식 행사 홍보를 하여 주목을 받은 쿠기는 돌이킬 수 없어서 전부 다 주려고 했던 간식을 이벤트처럼 위장하려고 한다.

이벤트의 내용은 다음과 같다.

서프라이즈! 다음과 같은 조건을 만족하는 학생들에게 스테이크를 드려요!

1. 임의로 연속된 학번의 학생들을 정해요!

2. 임의로 대상 학생들을 두 그룹으로 나눠요! 대신 한 그룹의 학생들은 학번이 인접해야 해요! 그룹에는 최소 한명의 학생이 있어야 해요!

3. 두 그룹의 스테이크 무게 합의 차 E를 구해요! E를 계산할 때는 합이 큰 그룹에서 작은 그룹의 합을 빼요!

4. 가능한 모든 경우에 대해 계산하여 E가 최솟값인 두 그룹의 학생들에게 스테이크를 드립니다!

5. 대신 최솟값이 같은 경우가 여러 가지라면 두 그룹의 스테이크 무게 합이 가장 큰 두 그룹의 학생들에게 스테이크를 드립니다!

예를 들면, 1번~6번 학생에 대한 설문 조사 결과가 [2, 1, 5, 2, 4, 4]일 때 다음과 같이 계산한다.

1. 임의로 연속되게 학번이 2인 학생부터 6인 학생까지 정한다.
2. 임의로 2~3번 학생의 그룹과 4~6번 학생의 그룹을 나눈다.
3. 2~3번 학생 그룹의 합은 6, 4~6번 학생 그룹의 합은 10이므로 E는 4이다.
4. 가능한 모든 경우에 대해 계산한다.
5. 해당 예시에 대한 답은 2~4번 학생 그룹과 5~6번 학생 그룹일 때 E가 최소이므로 2~6번 학생이 이벤트 당첨자다.

쿠기는 한시름 놨지만, 스테이크를 구매하기 위해 이벤트 당첨자들의 스테이크 무게의 합을 구하는 코드를 작성하려고 했는데 노트북이 망가졌다.

쿠기를 도와 당첨자들의 스테이크 무게 합을 구하는 프로그램을 작성하시오.

첫째 줄에 정수 N(2 ≤ N ≤ 2,000)이 주어진다.

다음 줄에 1번 학생부터 N번 학생까지 차례대로 설문 조사에 적은 스테이크의 무게를 나타내는 정수 W(1 ≤ W ≤ 10,000)가 주어진다.

이벤트에 당첨된 학생들의 스테이크 무게 합을 출력한다.