运羊过河

题目背景

在一个奇怪的梦里，艾莉带着一群羊来到河边。河对岸是一望无际的草场，她准备使用一艘船，将所有羊运到对岸。

为了决定每一趟带哪些羊，她坚持使用一种固定的贪心策略。现在她想知道：为了在规定趟数内运完所有羊，船的最小载重量是多少？

题目描述

共有 $N$ 只羊，第 $i$ 只羊的重量为 $w_i$。艾莉需要使用同一艘船将所有羊运到河对岸，船的载重量为 $C$。

每次从当前河岸渡河到草场、卸下羊并返回，计为一趟。每一趟中，艾莉严格按照以下贪心策略装船：

1. 在所有尚未运走、且能够装入当前船中的羊里，选择重量最大的一只装船；
2. 装入一只羊后，再从剩余的羊中选择重量最大、且与船上已有羊一起不会使总重量超过 $C$ 的羊装船；
3. 重复上述过程，直到没有任何剩余的羊能够继续装入船中；
4. 将本趟装入的羊运到对岸，然后开始下一趟。

重量相同的羊仍视为不同的羊。

若使用容量为 $C$ 的船，按照上述策略能够在不超过 $R$ 趟内运完所有羊，则称容量 $C$ 是可行的。

请你求出最小的可行容量 $C$。

输入格式

第一行包含两个整数 $N,R$，分别表示羊的数量和允许的最大趟数。

第二行包含 $N$ 个整数 $w_1,w_2,\ldots,w_N$，表示每只羊的重量。

输出格式

输出一个整数，表示船所需的最小载重量。

样例 1

输入

6 2
26 7 10 30 5 4

输出

42

解释

当船的容量为 $30$ 时，贪心策略依次得到：

• 第一趟：$30$；
• 第二趟：$26,4$；
• 第三趟：$10,7,5$。

需要三趟，超过限制。

当容量为 $42$ 时，贪心策略得到：

• 第一趟：$30,10$；
• 第二趟：$26,7,5,4$。

因此容量 $42$ 可行，并且它是最小可行容量。

注意，若不使用题目规定的贪心策略，容量 $41$ 可以通过其他装载方案在两趟内完成，但艾莉不会采用那些方案。

样例 2

输入

6 2
4 8 15 16 23 42

输出

54

样例 3

输入

15 4
666 42 7 13 400 511 600 200 202 111 313 94 280 72 42

输出

896

样例 4

输入

7 6
200 201 202 203 204 205 206

输出

401

数据范围

• $1\le N\le 2000$；
• $1\le R\le 2000$；
• $1\le w_i\le 2000$。

说明

• 艾莉自身的重量是固定值，可以忽略；
• 题目要求模拟的是给定的贪心策略，它不一定能得到全局最优的装载方案；
• 答案至少为最重羊的重量，至多为所有羊的重量之和。