Split a Long Hike Into Days

A trail is made of stages that must be walked in order, and stages[i] is the length of stage i in kilometres. You will walk the trail over exactly days days. Each day you walk one or more whole stages, carrying on from where the day before ended, so every stage is walked on exactly one day and every day has at least one stage.

Write longest_day(stages, days) that returns the smallest possible length of the longest day, over every way of splitting the stages into days.

Examples

longest_day([9, 3, 6, 11, 4], 2)     # returns 18
longest_day([5, 1, 1, 1, 5, 1], 3)   # returns 6
longest_day([4, 4, 4], 3)            # returns 4

In the first example the best plan walks 9 + 3 + 6 = 18 kilometres on day one and 11 + 4 = 15 on day two. Every other plan has a day longer than 18.

Constraints

• 1 <= days <= len(stages) <= 50,000
• 1 <= stages[i] <= 10,000

Note

Trying every way to place the breaks between days is hopeless for a trail of 50,000 stages.