25188번 - 1, 3, 모 나누기

문제

정모에게 다음과 같은 과제가 주어졌다!

"$N$개의 정수로 이루어진 수열 $a_1,a_2,\cdots, a_N$이 주어진다. 수열을 연속된 6ドル$개의 구간으로 나누고 각 구간을 왼쪽부터 차례대로 1ドル$번, 2ドル$번,$\cdots,ドル 6ドル$번 구간이라고 할 때, 1ドル$번, 3ドル$번, 5ドル$번 구간에 포함된 원소들의 합의 최댓값을 구하여라."

단, 모든 원소가 하나의 구간에 포함되어야 하고, 어떤 구간은 원소를 포함하지 않을 수도 있다. 만약 구간이 원소를 포함하지 않는다면, 구간 내 원소의 합은 0ドル$이다.

게으른 정모를 위해 과제의 답을 알려주자!

입력

첫째 줄에 수열의 길이 $N$이 주어진다. (1ドル \le N \le 2,000円$)

둘째 줄에는 수열 $a_1,a_2, \cdots, a_N$ 이 주어진다. ($-10^9 \le a_i \le 10^9$)

출력

첫째 줄에 과제의 답을 출력하라.

제한

힌트