Hiring

You have to hire workers for a construction project. There are $n$ candidates applying for the job, numbered from $1$ to $n$. Each candidate $k$ requires that if they are hired, they must be paid at least S_k dollars. Each candidate $k$ also has a qualification level Q_k. The construction industry regulations require that you pay your workers in proportion to their qualification level, relative to each other. For example, if you hire two workers $A$ and $B$, and Q_A = 3 Q_B, then you have to pay worker $A$ exactly three times as much as you pay worker $B$. You may pay your workers non-integer amounts of money. This includes amounts that cannot be written with a finite number of decimal digits, such as a third or a sixth of a dollar.

You have $w$ dollars and want to hire as many workers as possible. You decide whom to hire and how much to pay them, but you must meet the minimum salary requirements of those you hire and comply with the industry regulations. You must also keep within your budget of $w$ dollars.

For this construction project, the qualification level is irrelevant except for determining legal pay. You are only interested in maximizing the number of workers, regardless of their qualification level. However, if there are several ways to do this, you want to select the one where the total amount paid is minimized. If several ways remain, any one of them is acceptable.

Given the minimum salary requirements and qualification levels of the candidates, as well as the amount of money you have, write a program that determines which candidates you should hire. You must hire as many as possible, using as little money as possible, while complying with the industry regulations above.