最低运输能力

题目描述

n箱正重量货物必须按原顺序运输，每天运送一个连续段且总重量不超过容量C。求在D天内运完所需的最小容量。

输入格式

第一行输入n、D；第二行输入n个正整数重量，保证1≤D≤n。

输出格式

输出最小整数容量。

数据范围

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

样例

输入

6 3
3 2 2 4 1 4

输出

6