圣诞老人共有 𝑀 个饼干，准备全部分给 𝑁 个孩子。

每个孩子有一个贪婪度，第 𝑖 个孩子的贪婪度为 𝑔[𝑖]。

如果有 𝑎[𝑖] 个孩子拿到的饼干数比第 𝑖 个孩子多，那么第 𝑖 个孩子会产生 𝑔[𝑖]×𝑎[𝑖] 的怨气。

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

输入格式

第一行包含两个整数 𝑁,𝑀。

第二行包含 𝑁 个整数表示 $𝑔_1∼𝑔_𝑁$。

输出格式

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

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

数据范围

$1≤𝑁≤30,𝑁≤𝑀≤5000,1≤𝑔_𝑖≤10^7$

输入样例：

3 20
1 2 3

输出样例：

2
2 9 9