背景

题目描述

给定一个有 n 个正整数的数组。你的任务是将它分成 k 段，使得段内的最大和尽可能的小。

输入格式

第一行包含整数 n 和 k（1<=k<=n<=10⁵）。

第二行包含数组的元素 a_i（1<=a_i<=10⁹）。

输出格式

打印一个数字，段内可能的最小最大和。

样例

样例输入1

10 4
1 3 2 4 10 8 4 2 5 3

样例输出1

12

数据范围与提示