大样例下载

题目描述

幼儿园老师要把 $M$ 个苹果分给 $N$ 个小朋友。每个小朋友至少要分到一个苹果。苹果要全部分完。

第 $i$ 个小朋友希望分到 $W_i$ 个苹果。（$W_i$ 可能比 $M$ 还要大）

老师可能无法满足每个小朋友的愿望。

对于第 $i$ 个小朋友，如果有 $K_i$ 个小朋友分到的苹果数比他多，那么他就会产生 $K_i × W_i$ 的失望值。

问：如何分苹果，才能使所有小朋友的失望值之和（记为 $S$）最小？你需要输出 $S$ 的最小值，并且输出使得 $S$ 最小的一种分苹果方案。

输入格式

第一行：两个整数 $N, M$；

第二行：$N$ 个整数，依次表示第 $i$ 个小朋友希望分到的苹果数 $W_i$

输出格式

第一行：一个整数 $S$，表示所有小朋友失望值之和的最小值。

第二行：$N$ 个整数，依次表示第 $i$ 个小朋友分到的苹果数。如果有多种分法，只需要输出任意一种。

输入样例

3 20
1 2 3

##输出样例

2
2 9 9

数据范围

$1 ≤ N ≤ 50, N ≤ M ≤ 5000, 1 ≤ W_i ≤ 10^9$