139. Maximum Performance of a Team

Given n engineers with speed[i] and efficiency[i], choose at most k of them to maximize performance = (sum of chosen speeds) * (minimum chosen efficiency). Return the maximum performance modulo 10^9+7. Input: '[speed], [efficiency], k'.

Input: '[speed], [efficiency], k'.

Output: Integer mod 10^9+7.

Examples

Input: [2,10,3,1,5,8], [5,4,3,9,7,2], 2
Output: 60
Explanation: Engineers with speed 10 and 5, min efficiency 4 -> (10+5)*4=60.

Input: [2,10,3,1,5,8], [5,4,3,9,7,2], 3
Output: 68
Explanation: Three engineers.

Constraints

• 1<=k<=n<=10^5
• 1<=speed[i],efficiency[i]<=10^5

Asked by