Assume "A" is an array of "N" integers with a non-empty zero index and "K" is another integer. You must separate array "A" into "K" groups of consecutive elements

Size of the group is any integer such that , 0 <= size of group <= N. Every element of the array should belong to some group.  The sum of the group from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty group equals 0. The A-sum is defined as the maximal sum of any group.

For example, you are given integers 'K' = 3 and array A such that:

A[0] = 2

A[1] = 1

A[2] = 5

A[3] = 1

A[4] = 2

A[5] = 2

A[6] = 2 

The array can be divided, for example, into the following groups: 

[2, 1, 5, 1, 2, 2, 2], [], [] with a A-sum of 15;

[2], [1, 5, 1, 2], [2, 2] with a A-sum of 9;

[2, 1, 5], [], [1, 2, 2, 2] with a A-sum of 8;

[2, 1], [5, 1], [2, 2, 2] with a A-sum of 6.

The goal is to minimize the A-sum. In the above example, 6 is the minimal A-sum.

Given integer K and a non-empty zero-indexed array A consisting of N integers, returns the minimal A-sum. 

For example, given K = 3 and array A such that:

A[0] = 2

A[1] = 1

A[2] = 5

A[3] = 1

A[4] = 2

A[5] = 2

A[6] = 2 

the function should return 6, as explained above.

Assume that: 

• N and K are integers within the range [1..100,000];
• each element of array A is an integer within the range [0..5000].

Input :

• First Line: K : Number of groups.

• Second Line: N : Number of elements in the input array

• Third Line : Elements of array separated by space.

Output

• minimal A-sum

Sample

Input:

3
7
2 1 5 1 2 2 2

Output:

6

Input:

4
10
10 2 1 5 1 2 2 2 9 11 

Output:

12

Limit:

• Excecute time: 2s

• Memory: