7159: ABC252 —— F - Bread
[Creator : ]
Description
We have a loaf of bread of length $L$, which we will cut and distribute to $N$ children.
The i-th child ($1\leq i\leq N$) wants a loaf of length $A_i$.
Now, Takahashi will repeat the operation below to cut the loaf into lengths $A_1, A_2, \ldots, A_N$ for the children.
Find the minimum cost needed to distribute loaves to all children.
The i-th child ($1\leq i\leq N$) wants a loaf of length $A_i$.
Now, Takahashi will repeat the operation below to cut the loaf into lengths $A_1, A_2, \ldots, A_N$ 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$.Each child i must receive a loaf of length exactly $A_i$, but it is allowed to leave some loaves undistributed.
This operation incurs a cost of $k$ regardless of the value of $x$.
Find the minimum cost needed to distribute loaves to all children.
Input
Input is given from Standard Input in the following format:
$N\ L$
$A_1\ A_2\ \ldots\ A_N$
$N\ L$
$A_1\ A_2\ \ldots\ A_N$
Output
Print the minimum cost needed to distribute loaves to all children.
Constraints
$2≤N≤2×10^5$
$1\leq A_i\leq 10^9$
$A_1+A_2+\cdots+A_N\leq L\leq 10^{15}$
All values in input are integers
$1\leq A_i\leq 10^9$
$A_1+A_2+\cdots+A_N\leq L\leq 10^{15}$
All values in input are integers
Sample 1 Input
5 7
1 2 1 2 1
Sample 1 Output
16
Takahashi can cut the loaf for the children as follows.
- Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
- Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
- Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
- Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.
Sample 2 Input
3 1000000000000000
1000000000 1000000000 1000000000
Sample 2 Output
1000005000000000
Note that each child ii must receive a loaf of length exactly $A_i$.