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?


1 <= newspapers.length <= 10^5

1 <= newspaper <= 10^4

1 <= coworkers <= 10^5


Example 1:

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

Output: 18


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


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

Try it Yourself



Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions