整点巧克力
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题翻译自 [USACO 2010 Feb S] Chocolate Eating 。
\hspace{15pt}贝茜收到了 n 块巧克力，第 i 块巧克力能够提供给她 h_i 点快乐值。
\hspace{15pt}贝茜的初始快乐值为 0 ，每天结束前她会按照计划吃下若干块巧克力并获得快乐值，第二天开始时，由于经过了一整晚的睡眠，快乐值会减半（向下取整）。她想在接下来的 d 天内合理安排食用计划，使得这段时间内每天的最小快乐值最大。特别的，她必须按照顺序依次吃巧克力；每一天可以吃若干块巧克力、也可以不吃。
\hspace{15pt}请你帮助她确定每一块巧克力都应该在哪一天吃掉，以使得这段时间内每天结束时的最小快乐值最大。

输入描述:

\hspace{15pt}第一行输入两个整数 n,d \left(1 \leq n, d \leq 5 \times 10^4 \right) 代表巧克力的数量、你需要指定计划的天数。
\hspace{15pt}第二行输入 n 个整数 h_1, h_2, \cdots, h_n \left(1 \leq h_i \leq 10^6\right) 代表每块巧克力的快乐值。

输出描述:

\hspace{15pt}第一行输出一个整数，代表贝茜在这 d 天内每天结束时的最小快乐值的最大值。
\hspace{15pt}随后 n 行，第 i 行输出一个整数 p_i \left(1 \leq p_i \leq d\right) ，代表第 i 块巧克力应该在哪一天吃掉。这里的编号即输入顺序，从 1 开始。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

复制 
5 5
10
40
13
22
7

输出

复制 
24
1
1
3
4
5

说明

\hspace{15pt}在这个样例中：
\hspace{23pt}\bullet\,她将在第一天结束前吃掉前两块巧克力，这天的快乐值为 10+40=50 ；
\hspace{23pt}\bullet\,第二天开始时，快乐值减半为 \frac{50}{2}=25 ，而这一条她将不再额外吃巧克力，所以这天的快乐值就为 25 ；
\hspace{23pt}\bullet\,第三天开始时，快乐值减半为 \frac{25}{2}=12 ，与此同时她将吃掉第三块巧克力，这天的快乐值为 12+13=25 ；
\hspace{23pt}\bullet\,第四天开始时，快乐值减半为 \frac{25}{2}=12 ，与此同时她将吃掉第四块巧克力，这天的快乐值为 12+22=34 ；
\hspace{23pt}\bullet\,第五天开始时，快乐值减半为 \frac{34}{2}=17 ，与此同时她将吃掉第五块巧克力，这天的快乐值为 17+7=24 ；
\hspace{15pt}综上所述，贝茜在这 5 天内每天结束时的最小快乐值为 \min\left\{25, 25, 34, 24\right\}=24 ，我们可以证明这是最大的。