1336 - 开心吃巧克力

通过次数

2

提交次数

3

时间限制 : 1 秒
内存限制 : 128 MB

Bessie 拿到了 N1 \leq N \leq 5\times 10 ^ 4)块巧克力。她决定想个办法吃掉这些巧克力,使得它在吃巧克力的这段时间里,最不开心的一天尽可能的开心。并且一共吃 D1 \leq D \leq 5\times 10 ^ 4)天。

每块巧克力有一个开心值 H_i1 \leq H_i \leq 10 ^ 6),当某天你吃下那块巧克力时,你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上 Bessie 睡觉之后,它的开心值会减半。也就是说,比如昨天 Bessie 的开心值为 50,那么今天早上一醒来就会有 25 点的开心值,舍去小数点后数字。另外,Bessie 还有一个怪癖,她喜欢按照巧克力本来的排列顺序吃。

Bessie 第一天的开心值为 0,求一个每天吃巧克力的方案,使得 Bessie 最不开心的一天尽可能的开心。

输入

第一行:两个整数 ND,中间用空格分隔。

2 行至第 N + 1 行:每行一个整数,第 i + 1 行表示 H_i 的值。

输出

第一行:一个整数,表示 Bessie 在 D 天中最不开心的一天最大可能的开心值。

2 至第 n + 1 行,每行一个整数,第 i + 1 行表示 Bessie 吃第 i 块巧克力的日期。

样例

输入

5 5 
10 
40 
13 
22 
7

输出

24 
1 
1 
3 
4 
5

来源

USACO