205007 - 花费

某人的旅行天数为N(1≤N≤100 000),每天需要花的钱已经分配好,请把这些天分成M(1≤M≤N)份(每份都是连续的天),则第i段的钱数和为sum[i](i=1,2,…,M),求max{sum[i]}最小为多少?

Input

第一行为两个整数即N和M,第二行为N个数,表示每天的花费。

Output

输出分成M份后的最小和。

Examples

Input

7 5
200 300 300 200 500 221 420 

Output

500
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题