分数: 500 点
问题陈述
我们有一条很长的面包 L,我们将剪切并分发到 N 孩子们。
的 i第一个孩子 (1\leq i\leq N) 想要一条长度的面包 A_i.
现在,高桥将重复以下操作,将面包切成一定长度 A_1, A_2, \ldots, A_N 为了孩子们。
选择长度的面包 k 和一个整数 x 之间 1 和 k-1 (含)。将面包切成两个长度的面包 x 和 k-x.
此操作的成本为 k 无论值 x.
每个孩子 i 必须收到长度完全一致的面包 A_i,但允许留下一些面包不分发。
求向所有儿童分发面包所需的最低成本。
约束
- 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 费用为 3。将前者交给 1-st 孩子。
- 选择面包的长度 2 和 x=1,将其切成两个长度的面包 1 费用为 2。将它们交给 3-rd 和 5第一个孩子。
- 选择面包的长度 4 和 x=2,将其切成两个长度的面包 2 费用为 4。将它们交给 2-nd 和 4第一个孩子。
这会产生以下费用 7+3+2+4=16,这是可能的最小值。 不会有剩下的面包。
示例输入 2
3 1000000000000000 1000000000 1000000000 1000000000
示例输出 2
1000005000000000
请注意,每个孩子 i 必须收到长度完全一致的面包 A_i.