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