Construction#5226
Watson needs to construct the most effective neural network. He is provided with a board containing chips, placed in a line with a distance of cm between adjacent chips. Each chip has its own performance value, expressed by an integer. Watson can build any number of neurons using these chips; each chip can be used in at most one neuron. A neuron is formed by connecting two chips that are exactly cm apart. The effectiveness of a neuron is the sum of the performance values of its two chips. The effectiveness of a neural network is the sum of the effectiveness values of all its neurons. The neural network may consist of any number of neurons, including zero.
The first line contains two integers and .
The second line contains integers A_i — the performance values of the chips.
Output the maximum effectiveness of a neural network that can be constructed using the chips on the board.
Example 1