题目描述

给你一个有 n 个正整数元素的数列，要求把它划分成连续的 k 段，使每段元素和的最大值最小。

输入格式

输入第一行两个正整数 n,k，第二行为此数列 $a_i$。

输出格式

输出一行一个数，为题目所求答案（每段元素和的最大值）。

样例

输入#1

5 2
2 1 3 4 5

Copy

输出#1

9

Copy

数据范围

30% 数据 n≤30,k≤10

100% 数据n≤100000,k≤n,0≤$a_i$​≤$10^9$