题目描述

n件物品排成一排，编号分别为1、2、3...n，价值分别为a₁、a₂、a₃...aₙ。 请将这n件物品拆分为k组（不改变物品的顺序），要求每组内至少有一件物品，分别统计每组物品的价值之和，并找出其中的最大值。请设计一种分组方案，使这个最大值尽可能小，并输出这个最大值。

示例：n=5，物品价值为6、1、3、8、4，k=2，共有4种拆分方案：

1. [6]和[1,3,8,4]，组和分别为6和16，最大值为16
2. [6,1]和[3,8,4]，组和分别为7和15，最大值为15
3. [6,1,3]和[8,4]，组和分别为10和12，最大值为12
4. [6,1,3,8]和[4]，组和分别为18和4，最大值为18 其中第3种方案的最大值12是所有方案中最小的，故输出12。

输入格式

1. 第一行输入一个整数n(1≤n≤1000)，表示物品的数量
2. 第二行输入n个整数a₁、a₂...aₙ(1≤aᵢ≤10⁵)，表示对应物品的价值，整数之间用空格隔开
3. 第三行输入一个整数k(1≤k≤n)，表示拆分的组数

输出格式

输出一个整数，表示符合要求的组和最大值的最小可能值。

输入输出样例

输入

5
6 1 3 8 4
2

输出

12