Newspapers

You've begun working in the one and only Umbristan. As part of your job working for the government you are asked to organize newspapers. Each morning your fellow coworkers will dilligently read through the newspapers carefully examining its contents. It is your job to organize the newspapers into piles and hand them out to your coworkers to read through. Each newspaper is assigned a time based on how much time it would take to read through its contents. The newspapers are carefully layed out in a line in a particular order that must not be broken when assigning the newspapers. That is you cannot pick and choose newspapers to make a pile to assign to a co-worker to read through. Instead you must take a particular subsection of the line of newspapers, make a pile and give that to a co-worker.

What is the minimum amount of time it would take to have your coworkers go through all the newspapers?

Constraints

1 <= newspapers.length <= 10^5

1 <= newspaper <= 10^4

1 <= coworkers <= 10^5

Examples

Example 1:

Input: newspapers = [7,2,5,10,8], coworkers = 2

Output: 18

Explanation:

Assign first 3 newspapers to one coworker then assign the rest to another. The time it takes for the first 3 newspapers is 7 + 2 + 5 = 14 and for the last 2 is 10 + 8 = 18.

Example 2:

Input: newspapers = [2,3,5,7], coworkers = 3

Output: 7

Explanation:

Assign [2, 3], [5], and [7] separately to workers. The minimum time is 7.

Try it Yourself