138. Minimum Cost to Hire K Workers

There are n workers with quality[i] and minimum wage expectation wage[i]. Hire exactly k workers forming a paid group such that each worker is paid in proportion to quality within the group and at least their minimum wage. Return the least possible total cost, rounded to 5 decimal places. Input: '[quality], [wage], k'.

Input: '[quality], [wage], k'.

Output: Float string (5 decimals).

Examples

Input: [10,20,5], [70,50,30], 2
Output: 105.00000
Explanation: Hire workers 0 and 2.

Input: [3,1,10,10,1], [4,8,2,2,7], 3
Output: 30.66667
Explanation: Optimal group cost.

Constraints

• 1<=k<=n<=10^4
• 1<=quality[i],wage[i]<=10^4

Asked by