# Split the array with a minimum sum

Given

`n`

integers

and an integer `k`

, you are asked to split the array into `k`

contiguous parts so that the maximum subarray sum is as small as possible. Input

The first line of the input contains two integers

`n`

(1 ≤ n ≤ ) and `k`

(1 ≤ k ≤ n).The next line contains space-separated integers

( ≤ ≤ ). Output

The program should print the maximum subarray sum that is as small as possible.

Examples

Input | Output |

5 2
1 2 3 6 2 | 8 |

5 3
1 2 10 3 2 | 10 |

Explanation

`[1 2 3] [6 2]`

⇒ maximum subarray sum is 6 + 2 = 8

`[1 2] [10] [3 2]`

⇒ maximum subarray sum is 10

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB