Migrated from Lutece 1751 传送站

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在一条直线上有n个建筑，从左到右给定相邻建筑之间的距离dist[]数组，一个人一秒钟可以走一个单位长度，你可以在直线上建造k个传送站，传送站之间的传送不需要时间，设d(x,y)为从建筑物x到建筑物y的最短时间，对所有d(x,y)，请最小化其最大值并输出

Input

第一行，dist数组的大小，也就是n-1 第二行，dist数组 第三行，整数k

3<=n<=3000

2<=k<=n

dist中的元素不超过1e6

Output

如题面所述

Samples

3
3 5 4
3

3