/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ L のパンが 1 つあり、これを N 人の子供たちに切り分けます。 i 番目 (1\leq i\leq N) の子供は長さ A_i のパンを欲しがっています。
そこで、高橋君は次の操作を繰り返して、長さ A_1,A_2,\ldots,A_N のパンを切り出して配ることにしました。
長さ k のパン 1 つと 1 以上 k-1 以下の整数 x を選ぶ。選んだパンを長さ x のパンと 長さ k-x のパンに切り分ける。
このとき、x の値によらずコストが k かかる。
それぞれの子供に配るパンは長さがちょうど A_i のパン 1 つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。
このとき、全ての子供たちにパンを配るために必要な最小のコストを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L A_1 A_2 \ldots A_N
出力
全ての子供たちにパンを配るために必要な最小のコストを出力せよ。
入力例 1
5 7 1 2 1 2 1
出力例 1
16
高橋君は次のようにしてパンを切り分けて配ることができます。
- 長さ 7 のパンと整数 x=3 を選ぶ。パンは長さ 3 のパンと長さ 4 のパンに切り分けられる。 (コスト 7 )
- 長さ 3 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパンと長さ 2 のパンに切り分けられる。前者を 1 番目の子供に配る。 (コスト 3 )
- 長さ 2 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパン 2 つに切り分けられる。これを 3,5 番目の子供に配る。 (コスト 2 )
- 長さ 4 のパンと整数 x=2 を選ぶ。パンは長さ 2 のパン 2 つに切り分けられる。これを 2,4 番目の子供に配る。 (コスト 4 )
このとき、コストは 7+3+2+4=16 かかり、これが最小です。 また、余るパンはありません。
入力例 2
3 1000000000000000 1000000000 1000000000 1000000000
出力例 2
1000005000000000
それぞれの子供に配るパンの長さはちょうど A_i でなければならない事に注意してください。
Score : 500 points
Problem Statement
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.
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 A_i, but it is allowed to leave some loaves undistributed.
Find the minimum cost needed to distribute loaves to all children.
Constraints
- 2 \leq N \leq 2\times 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.
Input
Input is given from Standard Input in the following format:
N L A_1 A_2 \ldots A_N
Output
Print the minimum cost needed to distribute loaves to all children.
Sample Input 1
5 7 1 2 1 2 1
Sample Output 1
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.
This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.
Sample Input 2
3 1000000000000000 1000000000 1000000000 1000000000
Sample Output 2
1000005000000000
Note that each child i must receive a loaf of length exactly A_i.