题目描述

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

输入格式

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

输出格式

输出一行一个数，为题目所求答案。

样例

输入#1

5 2
2 1 3 4 5

输出#1

9

数据范围/约定

30% 数据 $n \leq 30, k \leq 10$

100% 数据 $n <= 100000, k \leq n, 0 \leq a_i \leq 10^9$