Background

IOI2009 D1T2.

Problem Description

You need to hire some workers for a construction project. There are $N$ candidate workers, numbered $1 \sim N$. Worker $k$ requires that if they are hired, they must be paid at least $S_k$ dollars. Each worker has a skill value $Q_k$. The Construction Industry Supervisory Bureau requires that you must distribute wages in proportion to the workers' skill values. For example, if $Q_A = 3Q_B$, then the wage you pay to $A$ must be exactly three times the wage you pay to $B$. You may pay your workers any non-negative real amounts.

You have $W$ dollars, and you want to use this money to hire the maximum possible number of workers. You may choose which workers to hire and how much to pay them, but you must satisfy each worker's minimum wage requirement and the Bureau's proportionality rule, and ensure that the total wage does not exceed $W$.

The workers' skill values are unrelated to your project, so you only want to maximize the number of hired workers and do not care about their skill values. Even so, you still want to minimize your spending. That is, if there are multiple feasible solutions, you must choose the one with the smallest total wage paid. If there are still multiple such solutions, any of them is acceptable.

Task: Write a program that, given each worker's wage requirement and skill value, and the amount of money you have, determines exactly which workers to hire. You must minimize spending while maximizing the number of workers hired, and satisfy the Bureau's rules described above.

Input Format

The first line contains two integers $N, W$ separated by spaces, representing the number of candidate workers and the amount of money you have.

The next $N$ lines each describe one candidate worker. Line $k$ describes candidate worker $k$ and contains two integers $S_k, Q_k$ separated by a space.

Output Format

The first line contains an integer $H$, the number of workers you hire.

The next $H$ lines each contain one integer, the indices of all hired workers (pairwise distinct), in any order.

4 100
5 1000
10 100
8 10
20 1

2
2
3

3 4
1 2
1 3
1 3

3
1
2
3

Hint

Sample Explanation

• Sample 1: Choosing workers $2$ and $3$ is the only solution that satisfies all requirements and hires two workers. You can pay them $80$ dollars and $8$ dollars respectively, meeting the $100$ dollar budget.

• Sample 2: You can hire three workers. You can pay them $1$ dollar, $1.5$ dollars, and $1.5$ dollars respectively.

Constraints and Notes

For any test point, if your solution satisfies all requirements and your objective, you will receive full score for that test point. Otherwise, if your first line is correct, meaning you output the correct number of hired workers $H$, then regardless of whether the rest of your output follows the format, you will receive $50\%$ of the score for that test point.

Note that in the actual evaluation, only if your output follows the format can you receive $50\%$ or $100\%$ for a test point.

• For $50\%$ of the testdata, $N \leq 5000$.
• For $100\%$ of the testdata, $1 \leq N \leq 5 \times 10 ^ 5$, $1 \leq S_k, Q_k \leq 2 \times 10 ^ 4$, $1 \leq W \leq 10 ^ {10}$.

Note that $W$ exceeds the storage range of 32-bit integer variables. You need to use a 64-bit integer variable to store $W$, such as long long in C/C++ or int64 in Pascal.

Translated by ChatGPT 5