最小运输能力

题目描述

n件正重量货物按原序分到不超过D天，每天一个连续段且总重≤C，求最小C。

输入格式

第一行n、D；第二行重量，保证1≤D≤n且总和在64位范围。

输出格式

输出最小容量。

数据范围

• $1 \le D \le n \le 2\times 10^5$；
• $1 \le a_i \le 10^9$，其中 $a_i$ 表示第 $i$ 件货物的重量。

样例

输入

10 5
1 2 3 4 5 6 7 8 9 10

输出

15