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