3921 - 工作计划的最低难度

通过次数

1

提交次数

5

时间限制 : 1 秒
内存限制 : 128 MB

你需要制定一份 d 天的工作计划表。要想执行第 i 项工作,你必须完成之前的所有工作。

你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和,而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 a 和一个整数 d,分别代表工作难度和需要计划的天数。第 i 项工作的难度是 a[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划,则返回 -1 。

输入

第一行一个整数 n , d表示工作的数量和天数

第二行包含n个整数,第 i 项工作的难度是 a[i]。

输出

仅一个数字,整个工作计划的 最小难度

样例

输入

6 2
6 5 4 3 2 1

输出

7

输入

3 3
1 1 1

输出

3

输入

3 4
9 9 9 

输出

-1

提示

第一组测试数据,前5个任务第一天做,第6个任务最后一天做,总难度为6

第二组测试数据,三个任务一天做一个,总难度为3

第三组测试数据,3个任务不可能分4天完成

n \leq 1000 , d \leq 20

来源

leetcode