The slowest speed that still finishes in time

Medium

2000 ms limit256 MB memoryBinary search Arrays

Stuck?

Show a hint

Binary search the speed, not the array. Every speed at or above the answer works and every one below fails, which is what makes halving valid.

The ideas behind this problem

Binary search, and getting the boundary right Binary search on the answer, when nothing is sorted

Next in this lesson

Two sum in a sorted list

There are piles of bananas and a number of hours available. Choose an eating speed in bananas per hour.

Each hour, one pile is eaten from. If the pile has fewer bananas left than the speed, the rest of that hour is wasted and the next hour starts a new pile. So a pile of p bananas at speed k takes ceil(p / k) hours.

Find the smallest speed that finishes every pile within the hours available.

Worked example#

For piles [3, 6, 7, 11] and 8 hours:

speed	hours needed	within 8?
1	3 + 6 + 7 + 11 = 27	no
2	2 + 3 + 4 + 6 = 15	no
3	1 + 2 + 3 + 4 = 10	no
4	1 + 2 + 2 + 3 = 8	yes
5	1 + 2 + 2 + 3 = 8	yes

The smallest that works is 4.

The idea#

You are not searching a sorted array here. You are searching a range of answers, from 1 up to the largest pile, which is the fastest speed that is ever useful.

What makes binary search apply is that the answer has a switch in it: every speed below the answer fails and every speed at or above it works. Once you know a speed works, nothing faster needs checking, and once you know it fails, nothing slower does either. So halve the range of speeds and test the middle one.

Testing a speed costs one pass over the piles, and there are about log(max pile) speeds to test.

Careful with the hours count. A hundred thousand piles of a billion bananas at speed 1 is 10^14 hours, which overflows a 32 bit integer. Total the hours in a 64 bit type.

Constraints#

1 <= number of piles <= 100000
1 <= piles[i] <= 1000000000
number of piles <= hours <= 1000000000

Input

piles is a count then that many integers. Then hours is one integer.

Output

The smallest workable speed.

Examples

Input

4
3 6 7 11
8

Output

Speed 4 needs exactly 8 hours, and speed 3 needs 10.

Input

5
30 11 23 4 20
5

Output

Five piles in five hours means a whole pile an hour, so the largest sets the speed.

Input

5
30 11 23 4 20
6

Output

One spare hour lets the 30 pile take two hours at speed 23.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.