← 返回题目列表

AtCoder · abc252_f

I. 面包

中文机器翻译题面 查看原题

分数: 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.