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$)

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