题目描述

一本书按顺序排好了 $n$ 叠纸，第 $i$ 叠有 $a_i$ 页，顺序不能打乱。装订时要把它做成 $k$ 卷，每卷都是连续的若干叠纸，并且每卷至少包含一叠纸。

一卷的厚度就是它包含的页数之和。为了翻阅方便，希望最厚的那一卷尽量薄。

求最厚一卷的最小可能厚度。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_i$。

输出格式

一行一个整数，表示最厚一卷的最小厚度。

输入输出样例 #1

输入 #1

6 3
4 2 4 5 1 1

输出 #1

7

说明

数据范围

• 对于 $100\%$ 的数据，$1\le k\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。