该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

一阵闹钟响起，你醒了，发现自己变回了人，并且是马上要上班的牛马实习生。

题目描述

这天，你接到了一个任务表，上面一共有 $n$ 个任务。并且这 $n$ 个任务存在严格的依赖关系，因此你必须严格按照 $1, 2, 3, \dots, n$ 的顺序依次执行它们。

已知第 $i$ 个任务需要花费 $t_i$ 的时间来完成。主管要求你必须在 $k$ 天内将所有任务全部做完。每天你可以选择连续完成若干个任务，也可以选择休息（即当天完成的任务数为 $0$），但每天完成的任务必须是完整且连续的。

为了防止过度劳累，你希望这 $k$ 天的工作时间尽可能平均。具体来说，请你制定一份任务分配计划，使得这 $k$ 天中耗时最多的一天所花费的时间尽可能小。

请输出这个最小的“单天最大花费时间”。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1\le k \le n \le 10^5$），分别表示任务的总数和规定的天数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$1\le t_i \le 10 ^9$），其中 $t_i$ 表示第 $i$ 个任务需要花费的时间。

输出格式

输出一个整数，表示在所有合法的分配方案中，单天最大花费时间的最小值。

样例

5 3
2 4 2 3 5

6

数据范围

共有 $25$ 组测试点。

对于前 $10$ 组测试点，$n$ 不超过 $10^3$。

对于后 $15$ 组测试点，$n$ 不超过 $10^5$。