说明

小C带领M-1个同学去比赛。在机场时轮到他们登记。机场一共有N个登记窗口，每一个窗口的工作效率不一定相同，所以登记的速度也不一定相同。对于第k个窗口，登记每一个乘客时需要时间为Tk。

在登记开始时，所有的窗口都是空闲的，可以立刻开始下一个人的登记工作，且当时只有小C和同学在进行登记。只有当前窗口空闲时才可以开始下一个人的登记工作。上一个人结束和下一个人开始之间衔接，以及每个人改变排队所在的窗口所消耗的时间忽略不计。

小C希望你能帮他计算出所有人完成登记所需的最小时间（不是每个人的耗时总和）。

输入格式

输入第一行，两个整数N和M，分别表示窗口的总数和总人数。1 ≤ N ≤ 10^5，1 ≤ M ≤ 10^9。

接下来N行，每行一个整数Tk，表示第k个窗口登记每一个乘客时所需要的时间。1 ≤ Tk ≤ 10^9。

输出格式

输出仅一行，表示最少所需的时间。

样例

输入：

2 6
7
10
7 10
3
8
3
6
9
2
4
    

输出：

28
8
    

数据范围与提示

对于75%的数据，M不大于300 000

样例