#3400. 饼干 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

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

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

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

输入格式

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

第二行包含N个整数表示

输出格式

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

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

样例

样例输入

3 20
1 2 3

样例输出

2
2 9 9

数据范围与提示

,

,