题目描述

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

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

小C希望你能帮他计算出所有人完成登记所需的最小时间。

输入格式

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

接下来N行，每行一个整数T$_k$(1<=T$_k$<=10$^9$)。

输出格式

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

样例

输入1

2 6
7
10

输出1

28

输入2

7 10
3
8
3
6
9
2
4

输出2

8

数据范围与提示

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