D - Minimum Width Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋くんは、N 個の単語からなる文章をウィンドウに表示させようとしています。 すべての単語の縦幅は等しく、i 番目 (1\leq i\leq N) の単語の横幅は L _ i です。

文章は、横幅 1 の空白を単語の区切りとしてウィンドウに表示されます。 より厳密には、高橋くんが横幅 W のウィンドウに文章を表示しているとき、次の条件が成り立っています。

  • 文章はいくつかの行に分かれている。
  • 1 番目の単語は一番上の行の先頭に表示されている。
  • i 番目 (2\leq i\leq N) の単語は、i-1 番目の単語の次に間隔を 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 行で出力せよ。

入力例 1

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

出力例 1

26

ウィンドウの横幅が 26 のとき、以下のようにして与えられた文章を 3 行に収めることができます。

ウィンドウの横幅が 25 以下のときは与えられた文章を 3 行に収めることができないため、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

Score : 400 points

Problem Statement

Takahashi is displaying a sentence with N words in a window. All words have the same height, and the width of the i-th word (1\leq i\leq N) is L _ i.

The words are displayed in the window separated by a space of width 1. More precisely, when the sentence is displayed in a window of width W, the following conditions are satisfied.

  • The sentence is divided into several lines.
  • The first word is displayed at the beginning of the top line.
  • The i-th word (2\leq i\leq N) is displayed either with a gap of 1 after the (i-1)-th word, or at the beginning of the line below the line containing the (i-1)-th word. It will not be displayed anywhere else.
  • The width of each line does not exceed W. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into M or fewer lines. Find the minimum possible width of the window.

Constraints

  • 1\leq M\leq N\leq2\times10 ^ 5
  • 1\leq L _ i\leq10^9\ (1\leq i\leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer in one line.

Sample Input 1

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

Sample Output 1

26

When the width of the window is 26, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is 25 or less, so print 26.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

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

Sample Output 2

10000000009

Note that the answer may not fit into a 32\operatorname{bit} integer.

Sample Input 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

Sample Output 3

189