题目背景

法尔伽大人可精了，学会魔法后踏空行走，硬说自己是风系主C。

题目描述

法尔伽大团长学会了魔法，给旅行者变出了 $n$ 堆摩拉，第 $i$ 堆有 $a_i$ 枚摩拉。 法尔伽答应旅行者把这些摩拉全部给旅行者，前提是旅行者帮助大团长解决下面的问题：

现在需要把这 $n$ 堆摩拉按原有顺序、不打乱、不分拆单堆，划分成恰好 $k$ 个连续小组。 定义一种划分方案的代价：为每个小组内所有堆摩拉数量之和的最大值。

请求出：所有合法划分方案里，代价的最小值。

输入格式

第一行两个正整数 $n,k$。 第二行 $n$ 个正整数，依次表示每一堆的摩拉数量。

输出格式

输出一个整数，表示所求最小代价。

样例输入

5 2
7 2 5 10 8

样例输出

18

样例解释

分为 $[7, 2, 5][10, 8]$两堆摩拉, 第一堆共有 $14$ 枚摩拉，第二堆共有 $18$ 枚摩拉，最大值为 $18$。可以证明，没有更优的方式使最大值更小。

数据范围

$1 \le k \le n \le 10^5$， $1\le a_i \le 10^9$