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

출력

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