描述

n 件物品排成一排，编号分别为: 1、 2、3,.., n，物品本身的价值分别为:$a_1, a_2, a_3, ..., 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 <= n <= 1000$) ，表示物品的数量 第二行输入 n 个整数 $a_1, a_2, a_3, ..., a_n$ ($1<=n<=10^5$) ， $a_i$ 表示 i 号物品的价值，整数之间以一个空格隔开

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

输出

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

样例数据

5
6 1 3 8 4
2

12