Hire the Cheapest Crew

A film studio needs exactly k workers for a job. Worker i has a skill level skill[i] and will not work for less than ask[i] coins. The studio pays its whole crew by one rule: it picks a single whole number rate, and every hired worker receives rate * skill[i] coins. Each hired worker must receive at least what they ask for.

Write cheapest_crew(skill, ask, k) that returns the smallest total number of coins the studio can pay for a crew of exactly k workers.

Examples

cheapest_crew([4, 2, 5, 3], [10, 9, 12, 6], 2)   # returns 21
cheapest_crew([3, 7], [10, 7], 1)                # returns 7
cheapest_crew([1, 2, 3], [5, 5, 5], 3)           # returns 30

In the first example the best crew is workers 0 and 3 at a rate of 3: they receive 12 and 9 coins, 21 in total. A rate of 2 would be too low for worker 0, who would get only 8 of the 10 coins they ask for.

Constraints

• 1 <= k <= len(skill) == len(ask) <= 100,000
• 1 <= skill[i], ask[i] <= 10,000

Note

Trying every crew is hopeless when there are many workers.