Competitions

# April 16 Contest

# Split into k sub-arrays

Given array of **n** elements and number **k**. Split the given array into **k** sub-arrays (they must cover all the elements). The maximum sub-array sum achievable out of **k** sub-arrays formed, must be minimum possible. Find that possible sub-array sum.

#### Input

First line contains two numbers **n** and **k** (**n** ≤ `10`

, ^{6}**1** ≤ **k** ≤ **n**). Second line contains **n** positive integers, each no more than `10`

.^{9}

#### Output

Print the minimum possible sub-array sum.

#### Explanation

For the first sample the optimal split is {**1**, **2**}, {**3**}, {**4**}. Maximum sum of all sub-arrays is **4**, which is minimum possible for **3** subarrays.

For the second sample the optimal split is {**1**, **2**, **3**, **4**}, {**2**, **3**, **4**}, {**2**, **3**, **1**}. Maximum sum of all sub-arrays is **10**, which is minimum possible for **3** subarrays.

Input example #1

4 3 1 2 3 4

Output example #1

4

Input example #2

10 3 1 2 3 4 2 3 4 2 3 1

Output example #2

10