P2884 [USACO07MAR] Monthly Expense S

题目描述

给定一个 $n$ 项的正整数序列 $\{a_n\}$，请找出满足以下条件的最小的正整数 $S$：存在一种将 $\{a_n\}$ 划分成 $m$ 段的方案，使得每一段中所有数字的和都不大于 $S$。

输入格式

第一行两个正整数 $n,m$。

下面 $n$ 行，每行一个正整数 $a_i$。

输出格式

一行一个正整数表示答案。

输入输出样例 #1

输入 #1

7 5
100
400
300
100
500
101
400

输出 #1

500

说明/提示

样例解释：$\{100,400\},\{300,100\},\{500\},\{101\},\{400\}$ 是一种合法的划分方案。

对于 $100\%$ 的数据，$1 \le m \le n \le 10^5$，$1 \le a_i \le 10^4$。