Chocolate Eating

Bessie has received $N$ ($1 \le N \le 50000$) chocolates, but she does not want to eat them too quickly. She wants to plan her chocolate-eating schedule for the next $D$ ($1 \le D \le 50000$) days so as to maximize the minimum happiness level she experiences over those days.

Bessie's happiness level is an integer that starts at $0$. Each night while she sleeps it halves, rounding down. When she eats chocolate $i$, her happiness level increases by the integer $H_i$ ($1 \le H_i \le 1000000$). If she eats one or more chocolates on a day, her happiness for that day is the happiness level after she has eaten them (her bedtime happiness). Bessie must eat the chocolates in the order she received them, and she may eat any number of chocolates (including zero) on a given day.

For example, consider $5$ chocolates whose happiness values are $(10, 40, 13, 22, 7)$, to be eaten over $5$ days. One optimal plan gives the following daily happiness:

The smallest bedtime happiness here is $24$, and no plan can make this minimum any larger, so the answer is $24$.

• Line 1: two space-separated integers $N$ and $D$.
• Lines 2 to $N+1$: line $i+1$ contains a single integer $H_i$.

• Print a single integer: the highest possible value of Bessie's minimum bedtime happiness over the $D$ days.