当前没有测试数据。

F - 面包

分数：$500$ 分

题目描述

我们有一块长度为 $L$ 的面包，我们需要将其切割并分给 $N$ 个孩子。
第 $i$ 个孩子 $(1\leq i\leq N)$ 想要一块长度为 $A_i$ 的面包。

现在，高桥将重复以下操作，将面包切割为长度为 $A_1, A_2, \ldots, A_N$ 的面包分给每个孩子。

选择一块长度为 $k$ 的面包和一个介于 $1$ 到 $k-1$ 的整数 $x$（包括边界）。将面包切割成长度为 $x$ 和 $k-x$ 的两块面包。
不论 $x$ 的取值如何，操作的成本都是 $k$。

每个孩子 $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$

输出

输出分给所有孩子所需的最小成本。

5 7
1 2 1 2 1

16

高桥可以按以下方式切割面包给孩子们。

• 选择长度为 $7$ 且 $x=3$ 的面包，将其切割成长度为 $3$ 和 $4$ 的面包，切割成本为 $7$。
• 选择长度为 $3$ 且 $x=1$ 的面包，将其切割成长度为 $1$ 和 $2$ 的面包，切割成本为 $3$。将第一个面包给第 $1$ 个孩子。
• 选择长度为 $2$ 且 $x=1$ 的面包，将其切割成两个长度为 $1$ 的面包，切割成本为 $2$。将它们分给第 $3$ 个和第 $5$ 个孩子。
• 选择长度为 $4$ 且 $x=2$ 的面包，将其切割成两个长度为 $2$ 的面包，切割成本为 $4$。将它们分给第 $2$ 个和第 $4$ 个孩子。

这样切割的成本为 $7+3+2+4=16$，最小成本。 没有剩余面包。

3 1000000000000000
1000000000 1000000000 1000000000

1000005000000000

注意，每个孩子 $i$ 必须收到一块长度精确为 $A_i$ 的面包。