题目描述

一条长跑路线被依次分成了 $n$ 段，第 $i$ 段长 $a_i$ 米。一支 $k$ 人的队伍要以接力的方式跑完全程，规则如下：

• 队员按顺序出发，每名队员跑连续的若干段，跑完后把接力棒交给下一名队员；
• 每一段恰好由一名队员跑，不能把一段拆开给两个人跑；
• 每名队员至少跑一段。

教练希望跑得最多的那名队员不要太累。请你帮忙安排，使得「跑得最多的队员所跑的总路程」尽可能小，输出这个最小值。

输入格式

第一行两个整数 $n, k$，分别表示路线的段数和队伍的人数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每一段的长度。

输出格式

一行一个整数，表示跑得最多的队员所跑总路程的最小可能值。

样例 #1

样例输入 #1

7 3
300 500 200 400 100 600 300

样例输出 #1

900

样例解释

一种最优安排是：第 $1$ 名队员跑前两段（$300 + 500 = 800$ 米），第 $2$ 名队员跑接下来三段（$200 + 400 + 100 = 700$ 米），第 $3$ 名队员跑最后两段（$600 + 300 = 900$ 米）。跑得最多的是 $900$ 米。

可以验证，无论怎样安排，都无法让每名队员都不超过 $899$ 米。

提示

数据范围

• 对于 $20\%$ 的数据：$n \le 10$；
• 对于 $50\%$ 的数据：$n \le 100$，$a_i \le 1000$；
• 对于 $80\%$ 的数据：$a_i \le 10^4$；
• 对于 $100\%$ 的数据：$1 \le k \le n \le 10^5$，$1 \le a_i \le 10^9$。

提示

• 如果每名队员最多跑 $x$ 米就能安排下来，那么每人最多跑 $x + 1$ 米当然也能安排下来。
• 全程总长可能超过 int 的范围。