题目描述

一个有n个正整数元素的集合，要求把它划分成k部分，使每部分元素和的最大值最小， 求这个最小值。

输入

输入第一行两个正整数n，k

第二行为此集合ai

输出

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

样例输入

5 2

2 1 3 4 5 样例输出

8

提示

30%数据 n <= 30, k <= 10

100%数据 n <= 100000, k <= 5000, 0<=ai <= 10^9