HZC 早闻 LWH 对数学研究颇深，于是带着以下问题去考他：对于给定的一个长度为N的正整数数列 A，现要将其分成 M 段，并要求每段连续，且每段和的最大值最小。

例如，将数列 [4, 2, 4, 5, 1] 要分成 3 段：

若分为 [4, 2][4, 5][1]，各段的和分别为 6, 9, 1，和的最大值为 9；

若分为 [4][2, 4][5, 1]，各段的和分别为 4, 6, 6，和的最大值为 6。

并且无论如何分段，最大值不会小于 6，所以可以得到要将数列 [4, 2, 4, 5, 1] 要分成 3 段，每段和的最大值最小为 6。

然而，LWH 只是外强中干，他开始虚了，现在请你帮他编程解决这个问题。

第 1 行包含两个正整数 N, M \ (1 \leq M \leq N \leq 10^5)。

第 2 行包含 N 个空格隔开的非负整数 a_1,a_2,...,a_N \ (1 \leq a_i \leq 10^9)，表示数列各项的值。

输入保证 \sum_{i=1}^N{a_i} \leq 10^9。

输出仅包含一个正整数，表示每段和最小的最大值。