#35. 「LYOI2016 Summer」Journey

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Menci

题目描述

小 Y 开始了一段旅途。

从起点到终点一共分为 n 段路,相邻的两段路间设有休息站。

小 Y 计划用最多 m 天走完全程,除第 m 天外,每一天小 Y 都必须在休息站过夜。所以,一段路必须在同一天走完。

小 Y 的体力有限,他希望走的路最多的一天中走的路尽可能少,请求出这个最小值。

输入格式

第一行两个正整数 n m ,分别路段数和天数。

从第二行开始,之后的 n 行,第 i 行为一个正整数 a_i ,表示第 i 段路的长度。

输出格式

一行一个正整数,表示小 Y 走的路最多的一天的路程最小值。

样例

输入样例

6 3
2
2
3
1
4
1

输出样例

5

数据范围与提示

对于 30\% 的数据, n, m \leq 10
对于 60\% 的数据, n \leq 900 m \leq 400
对于 100\% 的数据, 1 \leq n \leq 100000 1 \leq m \leq n 1 \leq a_i \leq 10 ^ {12}