545. Minimum Cost to Hire K Workers (Scaled)

There are n workers, each with a quality and a minimum wage expectation. You must hire exactly k workers forming a paid group, paying each in proportion to their quality relative to others in the group, and paying each at least their minimum wage. Return the least total cost. To keep the answer an exact integer, return floor(minCost * 100000). The input is JSON {quality, wage, k}.

Input: JSON {quality, wage, k}.

Output: Integer — floor(minCost * 100000).

Examples

Input: {"quality":[10,20,5],"wage":[70,50,30],"k":2}
Output: 10500000
Explanation: Min cost 105.0 scaled.

Input: {"quality":[1],"wage":[5],"k":1}
Output: 500000
Explanation: Single worker, cost 5.0.

Constraints

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

Asked by