Jono goes to school by teleportation. Jono lives in city $0$ and his school is in city $N$. Jono knows how to walk and teleport. However, after Jono teleports, Jono accumlates Chaos State, making him more and more tired after a teleportation. Formally, at city $i$, he has two options:

• Walk from city $i$ to city $i+1$, using up $a_i$ stamina
• Teleport $k$ cities ahead, i.e. from city $i$ to city $i+k$, using up $2^l$ stamina, where $l$ is the number of times teleporation has been used before this time. Note that you cannot teleport to a city beyond city $N$.

Can you help Jono to find at least how much stamina he needs to get to school?

Input

The first line of input contains two integers, $N$ and $k$. The second line contains $N$ integers, $a_i$, the stamina needed to walk from city $i$ to city $i+1$.

Output

Output a single integer, the minimum stamina needed for Jono to reach city $N$.

Constraints

For all testcases:
$1 \le N \le 10^6$
$1 \le k \le N$
$0 \le a_i \le 10^9$

Subtask 1 (20%): $1 \le N \le 1000$
Subtask 2 (80%): No other constraints