Earliest time for k jobs: hints, no solution

A render farm has several machines. Machine i finishes one job every minutes[i] minutes: its first job is done at minute minutes[i], its second at twice that, and so on, and all machines start together at minute 0 and never idle. Jobs are independent, so the farm needs k jobs completed in total and any machine may take any job.

Return the earliest minute at which at least k jobs have been finished across all machines. The answer can be far larger than 32 bits, so return a 64-bit integer. Trying every minute from 1 upward is too slow when k is a billion.

Examples

Input

minutes = [3, 5], k = 4

Output

9

Note

At minute 9 the first machine has done 3 jobs and the second 1, which reaches 4; at minute 8 only 3.

Input

minutes = [4], k = 3

Output

12

Note

Twelve minutes gives three completed jobs.

Constraints

• 1 <= minutes.length <= 2000
• 1 <= minutes[i] <= 10000
• 1 <= k <= 1000000000
• The result is at most 10000000000000

Hint 1: a nudge

Suppose someone proposes a deadline in minutes. Can you tell, without simulating, whether k jobs would be finished by then?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing