Rolling a Snowball

A snowman-building contest is held in the front yard of Sookmyung Women's University, a neighborhood where a lot of snow falls. The front yard has length $N$, and snow has piled up only from position $1$ to position $N$. At position $i$, there is $a_i$ of snow. The contest rule is to roll a snowball in the front yard for $M$ seconds to build a snowman. The snowball starts with size $1$ at position $0$.

Susu, who wants to build the biggest snowman, studied how to roll a snowball. Rolling or throwing the snowball takes 1 second.

1. Roll the snowball to the current position +1. If the current position is $i$, the snowball's size increases by $a_{i+1}$.
2. Throw the snowball to the current position +2. As it lands, the impact reduces the snowball's size to half of its original size, and if the current position is $i$, its size increases by $a_{i+2}$. Any fractional part is truncated. Even if the snowball's size becomes $0$ after a throw, the snowball does not disappear.

If the snowball reaches the end of the front yard, rolling ends regardless of the remaining time. Write a program that finds the largest snowball size achievable within the contest time.

The first line gives the length of the front yard $N$ ($1 \leq N \leq 100$) and the contest time $M$ ($1 \leq M \leq 10$), separated by a space.

The second line gives a sequence $a$ of length $N$. ($1 \leq a_i \leq 1\,000\,000$)

On the first line, print the largest snowball size achievable within the contest time.