（cake.cpp）

【问题描述】

ljz 是个吃货，她想要吃蛋糕。
ljz 一共有 n 个蛋糕，它们从左到右依次摆在一张桌子上，每个蛋糕有一个能量值。
因为 ljz 有强迫症，所以她想按从左到右的顺序吃蛋糕，并且一次只能吃连续的一段蛋糕。这 n 个蛋糕要全部吃完。
因为 ljz 的饭量是有限的，所以她一次只能吃下能量值总和不超过 K 的蛋糕。
因为 ljz 很怕自己长胖，所以她自欺欺人地认为，在吃下一段蛋糕后，这段蛋糕中，只有能量值最高的那个蛋糕的能量会被摄取。如果有多个蛋糕的能量值最大，也只会摄取其中一个蛋糕的能量。吃完 n 个蛋糕后摄取的总能量，就是吃每段蛋糕摄取的能量值。
那么，ljz 应当如何吃蛋糕，才能使摄取的总能量最小呢（按照 她认为的计算方式 ）？求出这个最小值即可。

【输入格式】

第 1 行，2 个整数\(n,K\)，表示共有\(n\)个蛋糕，且一次只能吃下能量值总和不超过\(K\)的蛋糕。
第 2 行，共\(n\)个整数，表示每个蛋糕的能量值\(w[i]\)。

【输出格式】

输出文件共 1 行，表示答案。

【输入输出样例 1】

cake.in

8 17
2 2 2 8 1 8 2 1 

cake.out

12

【数据规模与约定】

对于 5%的数据，\(1≤n≤20\)。
对于 40%的数据，\(1≤n≤5000\)。
另有 5%的数据，\(K\)大于等于所有蛋糕的能量值总和。
另有 10%的数据，所有蛋糕的能量值相等。
对于 100%的数据，\(1≤n≤100000,0≤w[i]≤1000000,K≤10^{11}\)，且\(K\)大于等于任意一个蛋糕的能量值。