Problem Description

Santa Claus has a total of $M$ cookies and plans to give them all to $N$ children.

Each child has a greed value. The greed value of the $i$-th child is $g_i$.

If there are $a_i$ children who receive more cookies than the $i$-th child, then the $i$-th child will have resentment of $g_i\times a_i$.

Given $N$, $M$, and the sequence $g$, please help Santa Claus find a distribution such that each child gets at least one cookie, and the total resentment of all children is minimized.

Input Format

The first line contains two integers $N, M$.

The second line contains $N$ integers representing $g_1, g_2, \dots, g_n$.

Output Format

The first line contains one integer, the minimum total resentment.

The second line contains $N$ integers separated by spaces, representing the number of cookies each child receives. If there are multiple solutions, output any one of them.

3 20
1 2 3

2
2 9 9

Hint

Constraints: $1\leq N\leq 30$, $N\leq M\leq 5000$, $1\leq g_i\leq 10^7$.

Translated by ChatGPT 5