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. [1 2 3] [6 2] β‡’ maximum subarray sum is 6 + 2 = 8
  1. [1 2] [10] [3 2] β‡’ maximum subarray sum is 10
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue