- Time limit: 2.00 s
- Memory limit: 512 MB
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