题目描述

圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]×a[i]的怨气。给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小1≤N≤30,N≤M≤5000, 1≤gi​≤107。

输入格式

第一行两个整数N,M，第二行N个整数g1​∼gN​。

输出格式

第一行一个整数表示答案，第二行N个整数表示每个孩子分到的饼干数。本题有SPJ，若有多种方案，输出任意一种均可。

样例

一
3 20
1 2 3
二
4 9
2 1 5 8

一
2
2 9 9
二
7
2 1 3 3