题目描述

贝西从大牛那里收到了 $n$ 块巧克力。她不想把它们马上吃完，而是打算制定一个计划，使得在接下来的 $d$ 天里，她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量，一开始的时候是 $0$，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺序来吃巧克力。当她吃掉第 $i$ 块巧克力的时候，她的快乐指数会增加 $h_i$。每天可以吃任意多块巧克力，如何帮助贝西合理安排，使得 $d$ 天内她的最小快乐指数最大呢？

举个例子：假设一共有五块巧克力，贝西打算在五天时间内将它们吃完，每块巧克力提供的快乐指数分别为 $10, 40, 13, 22, 7$。则最好的方案如下：

$$\boxed{ \begin{matrix} \text{天数}&\text{起床时快乐指数}&\text{食用的巧克力}&\text{就寝时快乐指数}\\ 1&0&{10+40}&50\\ 2&25&/&25\\ 3&12&13&25\\ 4&12&22&34\\ 5&17&7&24 \end{matrix} } $$

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

输入格式

第一行：两个用空格分开的整数：$n$ 和 $d$。

第二行到第 $n+1$ 行：第 $i+1$ 行表示第 $i$ 块巧克力提供的快乐指数 $h_i$。

输出格式

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

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

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

5 5
10
40
13
22
7

24
1
1
3
4
5

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n,d \leq5\times10^4$，$1 \leq h_i \leq 10^6$。

题目来源

Silver