机场检录

问题描述

小诚带领 $M-1$ 个同学去比赛,到机场后需要登记。机场一共有 $N$ 个登记窗口。每一个窗口的工作效率不一定相同,所以登记的速度也不一定相同。在第 $k$ 个窗口登记每一个乘客需要的时间为 $T_k$。

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

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

输入格式

第一行输入两个整数 $N$ ( $1≤N≤105$ )和 $M$ ( $1≤M≤109$ )分别表示窗口的总数和总人数。

第二行输入 $n$ 个数 $T_1$, $T_2$,…, $T_k$,表示每一个窗口的登记时间。

输出格式

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

输入输出样例】

样例输入

7 10	
3 8 3 6 9 2 4

样例输出

8