D - Transporting Cargo Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、1 から N までの番号がつけられた N 個の荷物を、最大 K 台のトラックを使って運ぼうとしています。荷物 i の重さは A_i です。

荷物 1, 2, \dots, N はこの順に一列に並んでおり、高橋君はこれらを並び順を保ったまま K 個以下の空でない連続する区間に分割し、区間ごとに 1 台のトラックに積んで運ぶことにしました。すべての荷物はちょうど 1 台のトラックに積まれます。

荷物を適切にトラックへ積み込んだとき、1 台のトラックに積まれる荷物の重さの合計の最大値として考えられる最小値を求めてください。

制約

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力に含まれる値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1
A_2
\vdots
A_N

出力

1 台のトラックに積まれる荷物の重さの合計の最大値として考えられる最小値を 1 行で出力してください。

入力例 1

5 3
1
2
3
4
5

出力例 1

6

入力例 2

4 2
10
20
30
40

出力例 2

60

入力例 3

10 4
15
23
8
37
12
9
45
18
22
31

出力例 3

63

入力例 4

25 7
45000000
120000000
89000000
230000000
67000000
150000000
310000000
78000000
420000000
190000000
88000000
260000000
530000000
140000000
95000000
370000000
610000000
280000000
170000000
490000000
330000000
820000000
210000000
560000000
130000000

出力例 4

1135000000

入力例 5

1 1
1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is trying to transport N packages, numbered 1 to N, using at most K trucks. The weight of package i is A_i.

Packages 1, 2, \dots, N are arranged in a row in this order. Takahashi has decided to divide them into at most K non-empty contiguous segments while preserving their order, and load each segment onto 1 truck to transport them. Every package is loaded onto exactly 1 truck.

When the packages are appropriately loaded onto the trucks, find the minimum possible value of the maximum total weight of packages loaded onto 1 truck.

Constraints

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

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

N K
A_1
A_2
\vdots
A_N

Output

Print the minimum possible value of the maximum total weight of packages loaded onto 1 truck in 1 line.

Sample Input 1

5 3
1
2
3
4
5

Sample Output 1

6

Sample Input 2

4 2
10
20
30
40

Sample Output 2

60

Sample Input 3

10 4
15
23
8
37
12
9
45
18
22
31

Sample Output 3

63

Sample Input 4

25 7
45000000
120000000
89000000
230000000
67000000
150000000
310000000
78000000
420000000
190000000
88000000
260000000
530000000
140000000
95000000
370000000
610000000
280000000
170000000
490000000
330000000
820000000
210000000
560000000
130000000

Sample Output 4

1135000000

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000