面包

题目描述

我们有一条长度为 $L$ 的面包，需要切开并分给 $N$ 个孩子。

第 $i$ 个孩子（$1 \le i \le N$）想要一条长度为 $A_i$ 的面包。

现在，高桥将重复以下操作，把面包切成孩子们需要的长度 $A_1, A_2, \ldots, A_N$。

选择一条长度为 $k$ 的面包，以及一个介于 $1$ 和 $k-1$（含端点）之间的整数 $x$。将面包切成两条长度分别为 $x$ 和 $k-x$ 的面包。

无论 $x$ 取何值，该操作都会产生 $k$ 的费用。

每个孩子 $i$ 必须得到一条长度恰好为 $A_i$ 的面包，但允许剩下一些没有分出去的面包。

求给所有孩子分发面包所需的最小费用。

输入格式

输入按以下格式从标准输入给出：

N L
A_1 A_2 … 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$ 的面包。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $A_1 + A_2 + \cdots + A_N \le L \le 10^{15}$
• 输入中的所有值均为整数。