[USACO10FEB] Chocolate Eating S

Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set of those days. Bessie's happiness level is an integer that starts at 0 and halves (rounding down if necessary) over night as she sleeps. However, when she eats chocolate i, her happiness level increases by integer H\_i (1 <= H\_i <= 1,000,000). If she eats chocolates on a day, her happiness for that day is considered the happiness level after she eats the chocolates. Bessie insists that she eat the chocolates in the order that she received them. If more than one optimal solution exists, print any one of them. Consider a sequence of 5 chocolates to be eaten over a period of 5 days; they respectively bring happiness (10, 40, 13, 22, 7). If Bessie eats the first chocolate (10 happiness) on the first day and then waits to eat the others, her happiness level is 10 after the first day. Here is the complete schedule which turns out to maximize her minimum happiness: Day Wakeup 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 minimum bedtime happiness is 24, which turns out to be the best Bessie can do. Bessie 拿到了 $N$（$1 \leq N \leq 5\times 10 ^ 4$）块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。并且一共吃 $D$（$1 \leq D \leq 5\times 10 ^ 4$）天。 每块巧克力有一个开心值 $H_i$（$1 \leq H_i \leq 10 ^ 6$），当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上 Bessie 睡觉之后，它的开心值会减半。也就是说，比如昨天 Bessie 的开心值为 $50$，那么今天早上一醒来就会有 $25$ 点的开心值，舍去小数点后数字。另外，Bessie 还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。 Bessie 第一天的开心值为 $0$，求一个每天吃巧克力的方案，使得 Bessie 最不开心的一天尽可能的开心。

\* Line 1: Two space separated integers: N and D \* Lines 2..N+1: Line i+1 contains a single integer: H\_i 第一行：两个整数 $N$ 和 $D$，中间用空格分隔。 第 $2$ 行至第 $N + 1$ 行：每行一个整数，第 $i + 1$ 行表示 $H_i$ 的值。

\* Line 1: A single integer, the highest Bessie's minimum happiness can be over the next D days \* Lines 2..N+1: Line i+1 contains an integer that is the day on which Bessie eats chocolate i 第一行：一个整数，表示 Bessie 在 $D$ 天中最不开心的一天最大可能的开心值。 第 $2$ 至第 $n + 1$ 行，每行一个整数，第 $i + 1$ 行表示 Bessie 吃第 $i$ 块巧克力的日期。

5 5 
10 
40 
13 
22 
7 

24 
1 
1 
3 
4 
5