题目描述

你有一根长度为 $L$ 的面包，现在你要将它分给 $N$ 个孩子，第 $i$ 个孩子想要一根长度为 $A_i$ 的面包。

对于一根长度为 $k$ 的面包，你可以选择一个在 $1 \sim k - 1$ 的整数 $x$，将面包切分成长度为 $x$ 和 $k - x$ 的两部分，这将花费 $k$ 的代价。

第 $i$ 个孩子获得的面包长度必须为 $A_i$，但我们允许有面包剩余。

请你花费最少的代价，将这根面包分给孩子们。

输入格式

第一行输入 $N$ $L$

第二行输入 $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出一个整数

5 7
1 2 1 2 1

16

3 1000000000000000
1000000000 1000000000 1000000000

1000005000000000

样例 1 解释

高桥可以按如下方法为孩子们切面包。

• 选择长度为 $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$ -nd和 $4$ -th的孩子。

这需要花费 $7+3+2+4=16$ ，这是可能的最低成本。不会有剩余的面包

提示

• $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}$