Description

漂亮的老师给幼儿园的小宝宝们发 n 个苹果，每个苹果有一个新鲜度，老师先把苹果排成一排，然后在不打乱顺序的情况下将这排苹果分成若干堆（也就是要求分成的若干堆里面的苹果要是连续的），且每堆总些新鲜度不超过 k ，请问每一堆的总新鲜度最大值之和最小是多少(有可能答案不存在)
如 5 个苹果新鲜度分别为 5 6 7 3 9 ，若 k 取 11 ，显然可以 5 6 为一堆， 7 3 为一堆， 9 为一堆，则答案是 6+7+9=22 且 22 为最优答案

Input

第一行输入两个整数 n 和 k
1<n,k<1e6
第二行输入 n 个整数，表示第 i 个苹果的新鲜度

Output

输出一个整数，表示答案
如果答案不存在，则输出 -1

Samples

5 10
2 6 5 8 4

23

3 2
4 5 6

-1

样例解释

对于样例一{(2，8）、（4，6）、（5）=8+6+5=19}更优但是分成的堆里面苹果不连续，所以不行 只能分成{（2，6）、（5）、（8）、（4）=6+5+8+4=23}

Limitation

1s, 1024KiB for each test case.