Minimum Cost to Hire K Workers

Hard

There are n workers. Worker i has quality nums[i] (first n/2 of the array) and minimum wage expectation nums[i] (second n/2). You want to hire exactly target workers. In a paid group, each worker is paid in proportion to their quality relative to the group, and each must receive at least their minimum wage. Return the minimum total cost (integer part) to hire exactly target workers.

Encoding: nums has 2k elements: first k are qualities, next k are wages. target is the number to hire.

Example 1

Input:  nums = [10,20,5,70,50,30], target = 2
Output: 105

Example 2

Input:  nums = [3,1,10,10,1,1], target = 2
Output: 2

Constraints

• 2 <= n <= 50 (n = nums.length / 2)
• 1 <= target <= n
• 1 <= quality[i], wage[i] <= 10^4