题目描述

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

每个孩子有一个贪婪度，第 $\red{i}$ 个孩子的贪婪度为 $\red{g_i}$。

如果有 $\red{a_i}$ 个孩子拿到的饼干数比第 $\red{i}$ 个孩子多，那么第$\red{ i}$ 个孩子会产生 $\red{g_i\times a_i}$的怨气。

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

输入格式

第一行包含两个整数$\red{N,M}$。

第二行包含$\red{N}$个整数表示$\red{g_1~g_N}$。

输出格式

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

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

$此题有\red{spj}，任意一种形式的答案都为正确$

输入样例

3 20
1 2 3

输出样例

2
2 9 9

提示

$\red{1≤N≤30}$,

$\red{N≤M≤5000}$,

$\red{1≤g_i≤10^7}$