Maximum Performance of a Team

There are n engineers. Engineer i has speed speed[i] and efficiency efficiency[i]. Choose a nonempty team containing at most k different engineers.

A team's performance is the sum of its members' speeds multiplied by the smallest efficiency among its members. Find the largest possible performance, then return it modulo 1000000007.

You may choose fewer than k engineers. Compare the full performance values before taking the modulo.

Example 1:

Input: n = 3
speed = [5,2,4]
efficiency = [3,9,6]
k = 2

Output: 36

Explanation: Choose the engineers with speeds 2 and 4. Their total speed is 6 and their minimum efficiency is 6, giving performance 36. No other team of at most two does better.

Example 2:

Input: n = 2
speed = [10,1]
efficiency = [10,1]
k = 2

Output: 100

Explanation: Choosing only the first engineer gives 10 × 10 = 100. Adding the second would reduce the minimum efficiency to 1 and give only 11, so the best team uses fewer than k engineers.

Example 3:

Input: n = 3
speed = [2,5,1]
efficiency = [7,3,9]
k = 3

Output: 24

Explanation: Choose the first two engineers: their total speed is 7 and minimum efficiency is 3, giving 21. Adding the last engineer increases the total speed to 8 without lowering the minimum efficiency, giving the optimal performance 24.

Constraints:

• 1 <= k <= n <= 100000
• speed.length == efficiency.length == n
• 1 <= speed[i] <= 100000
• 1 <= efficiency[i] <= 100000000