题目描述

POJ 3273

某人计算旅行天数为$\red{N（1≤N≤100 000）}$，每天需要花的钱已经分配好，请把这些天分成$\red{M（1≤M≤N）}$份（每份都是连续的天），则第$\red{i}$段的和为$\red{sum[i]（i＝1，2，…，M）}$，求$\red{max\{sum[i]\}}$最小为多少？

输入格式

第一行为两个整数即$\red{N}$和$\red{M}$，第二行为$\red{N}$个数，表示每天的花费。

输出格式

输出分成$\red{M}$份后的最小和。

样例

输入样例

7 5

200 300 300 200 500 221 420

输出样例

500