Score : 500 points
We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1≤i≤N) wants a loaf of length Ai.
Now, Takahashi will repeat the operation below to cut the loaf into lengths A1,A2,…,AN for the children.
Choose a loaf of length k and an integer x between 1 and k−1 (inclusive). Cut the loaf into two loaves of length x and k−x.
This operation incurs a cost of k regardless of the value of x.
Each child i must receive a loaf of length exactly Ai, but it is allowed to leave some loaves undistributed.
Find the minimum cost needed to distribute loaves to all children.
Input is given from Standard Input in the following format:
N L A1 A2 … AN
Print the minimum cost needed to distribute loaves to all children.
5 7 1 2 1 2 1
16
Takahashi can cut the loaf for the children as follows.
This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.
3 1000000000000000 1000000000 1000000000 1000000000
1000005000000000
Note that each child i must receive a loaf of length exactly Ai.