5492: 物品分组

n 件物品排成一排，编号分别为：1、2、3、...、n，每件物品都有它自身的价值，价值分别为：a1、a2、a3、...、an。请将这 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 个整数 a1、a2、...、an（1≤ai≤10^5），ai 表示 i 号物品的价值，整数之间以一个空格隔开。 第三行输入一个整数k（1≤k≤n），表示将 n 件物品拆分的组数

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

5
6 1 3 8 4
2

12