Description

Bessie拿到了N (1 <= N <= 50000)块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。

并且一共吃D (1 <= D <= 50000)天。

每块巧克力有一个开心值$H_i$ (1 <=$H_i$ <= 1000000)，当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。

每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上Bessie睡觉之后，它的开心值会减半。

也就是说，比如昨天Bessie的开心值为50，那么今天早上我一醒来我就会有25点的开心值，舍去小数点后数字。另外，Bessie还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。它同时也喜欢把好吃的留到最后，如果有多种吃巧克力的安排可以让最坏那天最好，它会选尽量延后去吃巧克力的那个安排

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

Format

Input

第1行：2个整数N和D

接下来N行，每行1个整数$H_i$

Output

第1行：1个整数，表示最不开心的一天的最大开心值

接下来N行，每行一个整数，表示第i块巧克力是第几天吃的

Samples

5 5
10
40
13
22
7

24
1
1
3
4
5

Limitation

1s, 1024KiB for each test case.