Chocolate Eating

Time limit1sMemory limit128 MB

Summary

Schedule N chocolates, eaten in fixed order over D days, to maximize the smallest bedtime happiness, where happiness halves each night and rises by eaten values.

Level: Medium7 of 10
Topics: Binary search, Greedy, Simulation, Implementation
Solved: No attempts yet

Problem

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:

Day	Wake-up happiness	Happiness from eating	Bedtime happiness
1	0	10 + 40	50
2	25	—	25
3	12	13	25
4	12	22	34
5	17	7	24

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

Input

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

Output

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

Examples2

Example 1
Input
```
5 5
10
40
13
22
7
```
Expected output
```
24
```
Example 2
Input
```
3 1
10
20
30
```
Expected output
```
60
```