Koko Eating Bananas

Annual Banana Festival is here in Umbristan. The Annual Banana Festival is one of the most renowned cultural celebration in Umbristan, and Koko is very excited because she loves eating bananas and banana foods. Banana smoothie, banana boat, you name it, she loves it.

Out of the n at the fair stands selling bananas, each stand sells a unique banana dish, Koko wants to try all of them. In fact, for the ith stand, Koko wants to have at least min_cals[i] Calories of food (Did you know that Calories and calories are different? 1 Cal = 1 kcal = 1000 cal). During each hour while the fair is open to the public, she can eat from one stand as much food as she wants.

Problem is, the fair is open to the public for a limited time - h hours to be exact - yet she would like to eat as much as she wants before the fair ends. However, as she is on a diet, she would like to reduce the max Calories of food she eats in an hour. You understand her struggle, so you would like to help.

Find the least maximum Calories she can eat per hour that allows her to eat what she wants before the fair closes for the public.

Input

  • min_cals: A list of Calories Koko wants to each from the food of each stand.
  • h: The number of hours the fair opens for.

Output

The least maximum Calories she can eat.

Examples

Example 1:

Input:

1min_cals = [3, 6, 7, 11]
2h = 8

Output: 4

Explanation:

For the eight hours that are open, Koko can do this:

  • For the 1st hour, eat 3 Cal from the first stand.
  • For the 2nd and the 3rd hour, eat 3 Cal each from the second stand.
  • For the 4th hour, eat 3 Cal from the third stand, and for the 5th hour, eat 4 Cal from it.
  • For the 6th hour, eat 3 Cal from the fourth stand, and for the next 2 hours, eat 4 Cal each.

Koko can finish eating everything she wants within 8 hours, with the max Calories per hour being 4.

Any smaller value will cause her to spend more time to eat, exceeding the time limit.

Constraints

  • 1 <= len(min_cals) <= 10^4
  • len(min_cals) <= h <= 10^9
  • 1 <= min_cals[i] <= 10^9

Try it yourself

Solution

Title

Script

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