月度开销分段优化

题目描述

连续n天正开销按原序划分为不超过m个非空连续月份段，最小化最大段开销。

输入格式

第一行n、m；第二行开销，保证1≤m≤n且总和在64位范围。

输出格式

输出最小可能最大段开销。

数据范围

• $1 \le m \le n \le 2\times 10^5$；
• $1 \le a_i \le 10^9$，其中 $a_i$ 表示第 $i$ 天的开销。

样例

输入

7 5
100 400 300 100 500 101 400

输出

500