You are given $n$ workers, each characterized by two attributes:

• quality[i]: Represents the work quality of the $i^{th}$ worker.

• wage[i]: Represents the minimum wage expectation of the $i^{th}$ worker.

You want to hire exactly k workers to form a paid group, and you must follow these payment rules:

1. Wage expectation: Every worker in the group must be paid at least their minimum wage expectation.

2. Proportional pay: The pay for each worker must be directly proportional to their quality. For example, if one worker’s quality is twice that of another, they must be paid twice as much.

Your goal is to determine the least amount of money required to hire exactly k workers while satisfying the above conditions.

Constraints

• n $==$ quality.length $==$ wage.length

• $1\leq$ k $\leq$ n $\leq 10^3$

• $1\leq$ quality[i], wage[i] $\leq 10^3$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.