T3 分面包（bread）

题目描述

面包店新烤出了 $n$ 块面包，它们按顺序排成一行，第 $i$ 块面包的重量为 $a_i$。店长要把这 $n$ 块面包按原来的顺序分成恰好 $k$ 个连续的非空小组，每个小组由若干相邻的面包组成。店长希望最重的那个小组的总重量尽可能小。

输入文件 bread.in，输出文件 bread.out。

请你求出这个最小的“最重小组总重量”。

输入格式

输入第一行包含两个正整数 $n,k$。

第二行包含 $n$ 个正整数 $a_i$，依次表示每块面包的重量。

输出格式

输出一行一个整数，表示答案。

样例 1 输入

5 2
1 2 3 4 5

样例 1 输出

9

样例 1 解释

分成 $2$ 个小组时，切在第 $3$ 块后面得到小组重量 $1+2+3=6$ 与 $4+5=9$，最重为 $9$，这是所有切法中最小的。

样例 2 输入

4 2
7 2 5 1

样例 2 输出

8

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 12$。
• 对于 $100\%$ 的数据，保证 $1 \le k \le n \le 10^5$，$1 \le a_i \le 10^9$。