由 $M$ 个人组成的克罗地亚代表团正准备前往澳大利亚参加 IOI 2013。他们目前正在机场排队办理登机手续。机场共有 $N$ 个开放的登机手续办理柜台。由于不同工作人员的工作效率不同，各个柜台的办理速度也有所不同。在第 $k$ 个柜台，办理一位旅客的登机手续需要 $T_k$ 秒。代表团成员恰好知道这些精确的时间。

最开始，所有柜台都准备好接待下一位旅客，且队列中只有代表团的成员。只有当队列中排在某个人前面的所有人都已经离开队列（即已经开始办理，但不一定完成办理）时，这个人才能占用（开始在）一个空闲的柜台。在那个时刻，这个人可以立即占用一个空闲的柜台（如果有的话），也可以选择等待另一个（更快的）柜台变得可用。作为计算机科学的热爱者，代表团成员们会做出决策，使得所有人全部完成登机手续的时刻尽可能早。你的任务是求出这个最早的时刻。

让我们以第一个样例为例来解释这个过程。有两个柜台，处理时间分别为 $7$ 秒和 $10$ 秒。在代表团的 $6$ 个人中，前两个人立即占用了这两个柜台。在时刻 $7$，第一个柜台空闲出来，第三个人占用了它。在时刻 $10$，第四个人占用了第二个柜台。在时刻 $14$，第五个人占用了第一个柜台。在时刻 $20$，第二个柜台再次空闲，但第六个人决定再等一秒（到时刻 $21$）以等待第一个柜台空闲并占用它。这样，所有人的登机手续在时刻 $28$ 全部完成。如果第六个人没有等待更快的柜台，那么办理完所有手续总共需要 $30$ 秒。

输入格式

输入的第一行包含两个正整数 $N$（$1 \le N \le 100\,000$），表示柜台的数量，和 $M$（$1 \le M \le 1\,000\,000\,000$），表示代表团的人数。

接下来的 $N$ 行，每行包含一个整数 $T_k$（$1 \le T_k \le 10^9$），表示题目描述中第 $k$ 个柜台的办理时间。

输出格式

输出的第一行也是唯一的一行，包含所需的最小时间（以秒为单位）。

子任务

在占总分 $75$ 分的测试数据中，数量 $M$ 将最多为 $300\,000$。

样例

输入样例 1

2 6
7
10

输出样例 1

28

输入样例 2

7 10
3
8
3
6
9
2
4

输出样例 2

8