#2016. [Usaco2010]Chocolate Eating

题目描述

贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完，而是打算制定一个计划，

使得在接下来的D天里，她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量，一开始的时候是0，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候，她的快乐指数会增加Hj。每天可以吃任意多块巧克力，如何帮助贝西合理安排，使得D天内她的最小快乐指数最大呢？

举个例子：假设一共有五块巧克力，贝西打算在五天时间内将它们吃完，每块巧克力提

供的快乐指数分别为10，40，13，22，7。则最好的方案如F：

天数

|

起床时快乐指数

|

食用的巧克力

|

就寝时快乐指数

---|---|---|---

1  
2  
3  
4  
5

|

0  
25  
12  
12  
17

|

10+ 40  

13  
22  
7

|

50  
25  
25  
34  
24  

|

|

|

五天内的最小快乐指数为24，这是所有吃法中的最大值。

输入格式

第一行：两个用空格分开的整数：N和D，1≤N．D≤50000

第二行到第N+1行：第1+1行表示第i块巧克力提供的快乐指数Hj，1≤Hi≤1000000

输出格式

第一行：单个整数，表示贝西在接下来D天内的最小快乐指数的最大值

第二行到第N+1:在第i+l行有一个整数，代表贝西应该在哪一天吃掉第i块巧克力。

如果有多种吃法，则输出按照词典序排序后最靠后的方案

样例

样例输入

55  

10  

40  

13  

22  

7  

样例输出

24  

 1  

 1  

 3  

 4  

 5  

数据范围与提示