← 返回题目列表

AtCoder · abc319_d

G. 最小宽度

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥正在显示一个句子 N 窗口中的文字。 所有单词的高度和宽度都相同 i- 第一个字 (1\leq i\leq N) is L _ i.

单词显示在窗口中,并以宽度间隔分隔 1。 更准确地说,当句子显示在宽度的窗口中时 W,满足以下条件。

  • 该句子分为几行。
  • 第一个单词显示在顶行的开头。 显示
  • 的 i- 第一个字 (2\leq i\leq N) ,间隙为 1 之后 (i-1)-第一个单词,或位于包含该行下方的行的开头 (i-1)- 第一个字。它不会在其他地方显示。
  • 每行宽度不超过 W。这里,线的宽度是指从最左边的单词的左端到最右边的单词的右端的距离。

当高桥在窗口中显示该句子时,该句子适合 M 或更少的行。 求出窗口的最小可能宽度。

约束

  • 1\leq M\leq N\leq2\times10 ^ 5
  • 1\leq L _ i\leq10^9\ (1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L _ 1 L _ 2 \ldots L _ N

输出

在一行中打印答案。


示例输入 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

示例输出 1

26

当窗口的宽度为 26,您可以将给定的句子分成三行,如下所示。

当窗口宽度为 25 或更少,因此打印 26.

请注意,您不应跨多行显示一个单词,不要让一行的宽度超过窗口的宽度,或者重新排列单词。


示例输入 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 2

10000000009

请注意,答案可能不适合 32\operatorname{bit} 整数。


示例输入 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

示例输出 3

189