题目描述

圣诞老人共有 $M$ 个饼干，准备全部分给 $N$ 个孩子。

每个孩子有一个贪婪度，第 $i$ 个孩子的贪婪度为 $g[i]$。

如果有 $a[i]$ 个孩子拿到的饼干数比第 $i$ 个孩子多，那么第 $i$ 个孩子会产生 $g[i] \times a[i]$ 的怨气。

给定 $N、M$ 和序列 $g$，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。

输入格式

第一行包含两个整数 $N, M$。

第二行包含 $N$ 个整数表示 $g_1 \sim g_N$。

输出格式

第一行一个整数表示最小怨气总和。

第二行 $N$ 个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。

样例

输入样例：

3 20
1 2 3

输出样例：

2
2 9 9

样例解释

$N=3, M=20$，贪婪度 $g=[1,2,3]$。

一种分配方案：孩子1分到 2 块，孩子2分到 9 块，孩子3分到 9 块。

计算怨气：

• 孩子1：比他多的有孩子2、3 → $a[1]=2$，怨气 $1\times 2=2$
• 孩子2：比他多的有谁？孩子2有 9 块，孩子3也有 9 块，没有比他多的 → $a[2]=0$，怨气 $2\times 0=0$
• 孩子3：同样 9 块，没有比他多的 → $a[3]=0$，怨气 $3\times 0=0$

总怨气 $2+0+0=2$。

可能存在更优方案？比如 $[7,7,6]$： 孩子1、2各 7 块，孩子3 6 块。 孩子3比孩子1、2少，$a[3]=2$，怨气 $3\times 2=6$。 孩子1、2没有比他们多的，怨气 0。 总怨气 6，比 2 大。

所以样例方案 $[2,9,9]$ 是一种最优方案。

数据范围

• $1 \le N \le 30$
• $N \le M \le 5000$
• $1 \le g_i \le 10^7$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB