Question
Fence Flash
Kiran plans to refresh his orchard’s fence, made of m panels with varying lengths in array arr[i]. He employs p workers, each painting 1 unit length per unit time. Each worker must paint a consecutive section of panels, like {1, 2} or {3}, not scattered ones like {1, 3}. All workers begin together, and Kiran seeks the fastest completion. Find the minimum time to paint the whole fence.
Input
The first line of the input contains the two space separated integer, n and p.
The next line of the input contains n space-separated elements, in a single line.
1 ≤ n ≤ 20
1 ≤ p ≤ 20
1 ≤ arr[i] ≤ 100
The next line of the input contains n space-separated elements, in a single line.
1 ≤ n ≤ 20
1 ≤ p ≤ 20
1 ≤ arr[i] ≤ 100
Output
Print the minimum time required to paint all partitions.
Example
Sample Input
4 2
10 20 30 40
Sample Output
60
Explanation
The most optimal way to paint:
Painter 1 allocation : {10, 20, 30}
Painter 2 allocation : {40}
Kiran will be complete at time = 60
4 2
10 20 30 40
Sample Output
60
Explanation
The most optimal way to paint:
Painter 1 allocation : {10, 20, 30}
Painter 2 allocation : {40}
Kiran will be complete at time = 60