Uolevi wants a yacht, but he is on a tight budget of $m$ euros, so he has decided to build his own.

He can spend money on buoyancy, size, and yellow paint. Formally, let $b$ be the amount of euros he spends on buoyancy, $s$ be the amount of euros spent on size, and $y$ the amount of euros spent on yellow paint. The value of the boat will be

$f(b) + f(s) + f(y)$

where $f: [0, m] \mapsto [0, 10^{9}]$ is some function you are given. Find the maximum value the boat can have when Uolevi spends at most $m$ euros in total, that is, he chooses $b$, $s$, $y$ such that

• $0 \leq b, s, y$
• $b + s + y \leq m$

Input

The first line contains an integer $m$.

The next line contains $m+1$ integers: $f(0), \dots, f(m)$.

Output

Output a single integer: the maximum value the boat can have.

Constraints

• $0 \leq m \leq 10^{4}$
• $0 \leq f(i) \leq 10^{9}$ for all $0 \leq i \leq m$

Example

Input:

11
1 0 5 9 10 2 16 13 0 19 27 6

Output:

30

Explanation:
Uolevi can choose $b = 2$, $s = 3$, $y = 6$ to achieve $30 = 5 + 9 + 16 = f(b) + f(s) + f(y)$.

Example 2

Input:

0
1000000000

Output:

3000000000