题目背景

EC-Final 前的最后一个月，Jiangrc 学长制定了一个为期 $N$ 天的“魔鬼冲刺计划”。每天的训练都有一个固定的压力值 $A_i$。 因为长时间高强度的训练会导致队友“红温”（指心态崩溃），Jiangrc 决定把这 $N$ 天划分成 $M$ 个连续的训练阶段。每个阶段结束时，队伍可以去吃一顿好的放松一下。 一个训练阶段的“总压力值”等于该阶段内所有天数的压力值之和。为了防止队伍在某个阶段彻底崩溃，Jiangrc 希望这 $M$ 个阶段中总压力值最大的那个阶段的压力值尽可能小。

题目描述

给定一个长度为 $N$ 的数组 $A$，表示每天的训练压力值。 你需要将这 $N$ 天划分为 $M$ 个连续的非空子段（每个元素恰好属于一个子段，且顺序不乱）。 求在所有可能的划分方案中，子段和的最大值最小是多少？

输入格式

第一行包含两个正整数 $N$ 和 $M$（$1 \le M \le N \le 10^5$），分别表示训练总天数和计划划分的阶段数。 第二行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^4$），表示每天的压力值。

输出格式

输出一个整数，表示在所有划分方案中，“最大连续子段和”的最小值。

样例

5 3
4 2 4 5 1

6

样例解释

将每天的训练划分为 $3$ 个阶段。最优的划分方法是： [4, 2]、[4]、[5, 1]。 这三个阶段的压力值之和分别为 $6, 4, 6$。 其中最大的阶段压力值为 $6$。可以证明找不到任何一种划分方案使得最大压力值 $< 6$。