Slowest speed that clears the queues

Problem

An agent has n queues of tickets, and queue i holds queues[i] tickets. Each hour the agent picks one queue and clears up to s tickets from it. Leftover time in an hour is wasted. Print the smallest whole s that clears all queues within the given hours.

Input, output and limits

Input: Line 1: n and hours. Line 2: n queue sizes.
Output: One integer: the smallest speed s.
Constraints: 1 ≤ n ≤ hours ≤ 10^9
1 ≤ n ≤ 10^5
1 ≤ queue size ≤ 10^9

Examples

Example

Input

4 8
3 6 7 11

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

A higher speed never needs more hours, so search the speed between 1 and the largest queue.

Hint 2

Hours for a speed s: add (queue + s - 1) // s for every queue.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Smallest truck for the parcelsmedium
The k-th missing numbermedium
Top of a visitor curvemedium
Look up a code in a sorted gridmedium
Find a value in a rotated listmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems