Question
Fence Painting Challenge
Raj decided to repaint the fence around his garden. The fence consists of n wooden panels, each of a different length, represented by the array arr[i].
To speed things up, Raj hired k painters to help him. Each painter works at a pace of 1 unit length per unit time, but there’s a condition: each painter can only paint a continuous section of the panels.
For example, a painter can take on panels {2, 3, 4} or just panel {1}, but they can’t handle non-continuous panels like {2, 4, 5}.
All the painters start at the same time, and Raj wants to finish the job as quickly as possible.
Help Raj figure out the minimum time required to paint the entire fence under these conditions.
Input
The first line of the input contains the two space separated integer, n and k.
The next line of the input contains n space-separated elements, in a single line.
The next line of the input contains n space-separated elements, in a single line.
Output
Print the minimum time required to paint all panels.
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}
Job 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}
Job will be complete at time = 60