1262 - 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

输入

第一行为整数n,表示数组中有n个整数

第二行为个整数,表示数组中的元素

第三行为整数m,表示要分割的组数

输出

m个子数组各自和的最大值

样例

输入

5
7 2 5 10 8
2

输出

18

输入

5
1 2 3 4 5
2

输出

9

输入

3
1 4 4
3

输出

4

提示

1 \leq nums.length \leq 1000

0 \leq nums[i] \leq 10^6

1 \leq m \leq min(50, nums.length)

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题