问题描述

具体描述见教材p226： 有n个同学一起去探险，现在把n个同学分成k个小组，每个小组完成一项探险任。分组时，如果第 i 人到第 j 人分在同一组 (i<j) ，则他们之间的所有人(第 i+1，i+2, ... , j-1)也必须在同一个小组中。 一个小组内所有人的体力和越小，途中可能越危险。 为了确保每个同学的安全，要求分组时，使得所有小组中，体力和最小的那个小组的所有人的体力和尽量大。 依次告诉你每个人的体力，如何分组呢?

格式

输入

第1行有两个正整数n和k，用一个空格分隔； 第2行有n个用空格分隔的正整数，表示n个人的体力值。

输出

只有1行，该行只有一个整数，表示最佳划分方案中，最弱的小组中，所有人的体力值之和。

样例

5 2
5 2 1 6 9

9

5 3
5 2 1 6 9

7

5 4
5 2 1 6 9

3

限制

1s, 64MB.