1, 3, 5 Segments

Interview

Time limit1.35sMemory limit1024 MB

Summary

Split a sequence of N integers into 6 contiguous segments (empty segments allowed) to maximize the sum of segments 1, 3, and 5.

Level: Medium4 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Odd Segments

Jeongmo has been given the following assignment.

"Given a sequence of $N$ integers $a_1, a_2, \cdots, a_N$ , split the sequence into $6$ contiguous segments. Number the segments $1$ st, $2$ nd, $\cdots$ , $6$ th from left to right. Find the maximum possible sum of the elements contained in segments $1$ , $3$ , and $5$ ."

Every element must belong to exactly one segment, and a segment may contain no elements. If a segment contains no elements, the sum of its elements is $0$ .

Tell Jeongmo the answer so the lazy student can skip the work!

Input

The first line contains the length of the sequence $N$ . ( $1 \le N \le 2\,000$ )

The second line contains the sequence $a_1, a_2, \cdots, a_N$ . ( $-10^9 \le a_i \le 10^9$ )

Output

Print the answer to the assignment on the first line.

Examples4

Example 1

Input

4
999999999 999999999 999999999 999999999

Expected output

3999999996

Example 2
Input
```
6
1 -2 3 5 -1 6
```
Expected output
```
15
```
Example 3
Input
```
1
-1
```
Expected output
```
0
```
Example 4
Input
```
12
-4 2 -1 2 -4 2 -2 2 -4 2 -1 2
```
Expected output
```
6
```