Rabbits

Memory limit: 256 MB

Byteasar has decided to grow lettuce in his garden. As you can imagine, Bytean rabbits simply love lettuce. So, not surprisingly, they instantly arrived in Byteasar's garden.

In the garden there are beds of lettuce numbered through . Every two subsequent beds are adjacent, that is, for each the beds number and are adjacent and, moreover, the bed number is adjacent to the bed number . Right now there are rabbits staying at the bed number and eating away Byteasar's lettuce.

Byteasar wants to chase out of the garden as many rabbits as possible. For this he is going to use his good old gun. The gun has bullets inside. Rabbits are extremely timid, so whenever Byteasar shoots towards the bed number , all the rabbits from that bed leave Byteasar's garden for good. What is more, the rabbits from both adjacent beds are so frightened that they all move to the adjacent bed (obviously, we mean the adjacent bed different from the one towards which was the shot).

Help Byteasar to find the maximum number of rabbits that he can chase out of his garden with at most shots.

Input

The first line of input contains two integers and (, ): the number of beds of lettuce in the garden and the number of bullets Byteasar has in his gun. The second line holds integers (): the number of rabbits staying at the subsequent beds.

Output

Your program should output one integer: the maximum number of rabbits that can be chased out of Byteasar's garden using at most shots.

Example

For the input data:

5 2
6 1 5 3 4

the correct result is:

13

Explanation of the example: First, Byteasar chases out the 6 rabbits from the bed number 1 (as a result, the rabbits from the bed number 5 move to the bed number 4, whereas the rabbits from the bed number 2 move to the bed number 3). Next, Byteasar chases out the 7 rabbits from the bed number 4.

Task author: Tomasz Idziaszek.