虽然名声被毁,但是 zzj 实际上并不是人渣,现在他打算继续跟 liaoy 一起完成他们神秘的魔法仪式。
在找到了魔力三角区域之后,他们试图聚集大量的魔力。现在有 瓶不同的魔力药水排成一排,每瓶魔力药水有一个魔力值。需要在这一排药水中间划 条分割线,来把它们分成 组,并且希望尽可能分得均匀。
此时 zzj & liaoy 需要知道如何分组才能使得 魔力值总和最高 的那一组药水的魔力值总和最小(不希望有某一组魔力值总和太多)。
第一行包括两个整数。
第二行n个整数,按顺序表示了这一排魔力药水的魔力值。
输出一个整数表示答案,即魔力值总和最大的一组药水的魔力值总和至少是多少。
4 2 12 24 9 8
36
4 3 12 24 9 8
24
4 3 12 15 9 8
17
药水魔力值
样例1分组方案:[12, 24], [9, 8]
样例2分组方案:[12], [24], [9, 8]
样例3分组方案:[12], [15], [9, 8]