问题描述

$n$ 件物品排成一排，编号分别为: $1、2、3、\dots、 n$ ；价值分别为:$a_1、a_2、a_3、\dots a_n$

请将这 $n$ 件物品拆分为 $k$ 组(不改变物品的顺序)，要求每组内至少有一件物品，分别统计每组物品的价值之和，并找出其中的最大值。

请设计一种分组方案，使这个最大值尽可能小，并输出这个最大值。

例如 n=5，表示有5 件物品，这5 件物品的价值分别是 6、1、3、8、4; k=2 ，表示要将这 5 件物品拆分为两组，有如下方案:

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，在 4 种方案中最小，故输出12。

输入描述

第一行 输入一个整数 $n$( $1 \le n \le 1000$ )，表示物品的数量。

第二行 输入 $n$ 个整数 $a_1、a_2、 \dots 、a_n$( $1 \le a_i \le 10^5$ )，$a_i$ 表示 $i$ 号物品的价值，整数之间以一个空格隔开

第三行 输入一个整数 $k$ ( $1 \le k \le n$ )，表示将 $n$ 件物品拆分的组数。

输出描述

输出一个整数，表示按照题目要求得到的最大值。

样例

5
6 1 3 8 4
2

12