P10971 Cookies

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.

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

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.

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