1268 - 小张刷题计划

为了提高自己的代码能力,小张制定了 LeetCode 刷题计划,他选中了 LeetCode 题库中的 n 道题,编号从 0n-1,并计划在 m 天内按照题目编号顺序刷完所有的题目(注意,小张不能用多天完成同一题)。

在小张刷题计划中,小张需要用 time[i] 的时间完成编号 i 的题目。此外,小张还可以使用场外求助功能,通过询问他的好朋友小杨题目的解法,可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”,小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T(小杨完成的题目不计入做题总时间)。请你帮小张求出最小的 T是多少。

输入

第一行为1个整数n,表示选定了n道题目。

第二行为n个整数,表示做每道题目需要的时间。

第三行为1个整数m, 表示m天做完全部题目。

输出

m天做完全部题目时,最小的做题时间 T

样例

输入

4
1 2 3 3
2

输出

3

输入

3
999 999 999
4

输出

0

提示

1 \leq time.lenght \leq 10^5

1 \leq time[i] \leq 10000

1\leq m \leq 1000

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