题目描述

我们有一条长度为 $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$

输出

打印分配面包给所有孩子所需的最小代价。

示例输入 1

5 7
1 2 1 2 1

示例输出 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$，这是最小可能的代价。不会有剩下的面包。

示例输入 2

3 1000000000000000
1000000000 1000000000 1000000000

示例输出 2

1000005000000000

请注意，每个孩子 $i$ 必须得到一块长度恰好为 $A_i$ 的面包。