19047번 - Inheritance 스페셜 저지다국어

You are the proud owner of $K$ apples. You want to leave them as inheritance to your children and grandchildren. You have $N$ children. Each of these children has children of their own. The array $\mathit{grand}[]$ describes this: its $i$-th value is equal to the number of children your $i$-th child has. So, your total number of grandchildren is equal to $\mathit{grand}[1] + \mathit{grand}[2] + \ldots + \mathit{grand}[N]$. It is guaranteed that $\mathit{grand}[i] \ge 1$ for all $1 \le i \le N$.

You must decide how many apples you will give to each of your children. You must distribute all $K$ apples, none may remain. Also, you many only distribute whole apples. After you distribute the apples among your children, they will redistribute the apples between their children. Because you want to be as fair as possible, you want to find the minimum value $\mathit{DIFF}$ such that:

• The difference between the maximum number of apples given to a child and the minimum number of apples given to a child does not exceed $\mathit{DIFF}$.
• The difference between the maximum number of apples given to a grandchild and the minimum number of apples given to a grandchild does not exceed $\mathit{DIFF}$.

Because your children are fair as well, you may assume that they will redistribute the apples given to them in such a way that $\mathit{DIFF}$ will be kept as small as possible. It is, however, up to you to decide how many apples you will give to each direct child of yours.

Output the minimum possible value $\mathit{DIFF}$ and the quantities of apples given to each child to achieve this value.

The first line of input contains two integers $N$ and $K$ ($1 \le N \le 1\,000\,000$, $1 \le K \le 10^{18}$).

The second line contains $N$ integers, the $i$-th of them is $\mathit{grand}[i]$. The total number of grandchildren does not exceed $2 \cdot 10^9$.

The first line must contain the value $\mathit{DIFF}$. The second line must contain $N$ non-negative integers: the number of apples given to each child. The sum of these integers must be equal to $K$. Any distribution of apples that leads to the correct value of $\mathit{DIFF}$ will be accepted.

If you give 43 apples to your first child and 57 apples to your second child, they will split them in the following way. The first child will give all 43 apples to his only child. The second child will give 28 apples to one of her children and 29 apples to the other.

The maximum difference between apples received by children is $57 - 43 = 14$. The maximum difference between apples received by grandchildren is $43 - 28 = 15$.