Maximize Worker Hiring Under Wage Proportion Constraints

You are given N candidate workers (numbered from 1 to N). The k-th worker requires a minimum wage of \(S_k\) dollars if hired, and has an ability value of \(Q_k\). According to the regulations, if two workers A and B have abilities such that \(Q_A = 3Q_B\), then the wage for worker A must be exactly three times that of worker B. In general, if you hire a set \(S\) of workers, you must assign them wages in exact proportion to their abilities. That is, there exists a constant \(c\) (which may be any nonnegative real number) such that for every worker \(i \in S\), the wage given is \(c \times Q_i\>.

However, each worker’s minimum requirement must be met, i.e., for every \(i \in S\), it must hold that \(c \times Q_i \ge S_i\). Thus the smallest possible constant you can choose is \[ c = \max_{i\in S}\frac{S_i}{Q_i}.\] The total wage paid is then \(c \times \sum_{i\in S} Q_i\), which must not exceed the available budget \(W\).

Your goal is to select a subset of workers that maximizes the number hired. In the case of multiple selections with the same maximum number, choose the selection that minimizes the total expenditure \(c \times \sum_{i\in S} Q_i\). If there are still multiple valid selections, any one of them is acceptable.

Task: Given \(N\), \(W\), and for each worker the values \(S_k\) and \(Q_k\), determine which workers to hire. Output the number of hired workers on the first line and the sorted (in increasing order) indices of these workers on the second line.

inputFormat

The input consists of multiple lines. The first line contains two numbers: an integer \(N\) (the number of candidate workers) and a real number \(W\) (the available budget).

Then \(N\) lines follow. The \(k\)-th of these lines contains two numbers \(S_k\) and \(Q_k\) representing the minimum wage required and the ability of the \(k\)-th worker, respectively.

outputFormat

Output two lines. The first line should contain a single integer denoting the maximum number of workers that can be hired under the regulations and budget. The second line should list the indices of the chosen workers in increasing order, separated by spaces. If no worker can be hired, output 0 on the first line and leave the second line empty.

sample

3 100
10 1
20 2
30 3

3
1 2 3