{"raw_statement":[{"iden":"background","content":"IOI2009 D1T2"},{"iden":"statement","content":"你需要为一个建设项目雇佣一些工人。现在有 $N$ 位候选工人，标号为 $1\\sim N$。第 $k$ 个工人要求如果自己被雇佣，则必须得到至少 $S_k$ 美元的工资。每个工人有能力值 $Q_k$。建筑业监管局规定，你必须按工人们的能力值的比例分配他们的工资。例如，如果 $Q_A = 3Q_B$，则你付给 $A$ 的工资必须恰为 $B$ 的三倍。你可以付给你的工人们任意非负实数金额的工资。\n\n你的手上有 $W$ 美元，你想用这些钱雇佣最大数量的工人。你可以决定选用哪些工人以及付给他们的工资，但必须满足每个工人的最低工资要求以及监管局的分配规定，并保证工资总额不超过 $W$。\n\n工人们的能力值和你的项目无关，因此你只想最大化雇佣工人的数量，而不关心他们的能力值。尽管如此，你仍希望最小化你的支出，即如果存在多种方案，则你需要选择支付给工人们的工资总额最小的那一个。如果仍存在多种方案，任意一个都是满足要求的。\n\n**任务**：编写一个程序，给定每个工人的工资要求和能力值，以及你拥有的资金，计算出具体雇佣哪些工人。你必须在最大化工人的数量的前提下最小化支出，并满足上文提到的监管局的要求。"},{"iden":"input","content":"第一行包含两个由空格隔开的整数 $N, W$，分别表示候选工人数和你拥有的资金。\n\n接下来 $N$ 行，每行描述一个候选工人。其中第 $k$ 行描述第 $k$ 个候选工人，包含两个由空格隔开的整数 $S_k, Q_k$。"},{"iden":"output","content":"第一行一个整数 $H$，表示你雇佣的工人数量。\n\n接下来 $H$ 行，每行一个整数，表示你雇佣的所有工人的编号（互不相同），以任意顺序排列。"},{"iden":"note","content":"### 样例解释\n\n- 样例 1：选择工人 $2$ 和 $3$ 是唯一符合所有要求且雇佣了两个工人的方案。你可以分别付给他们 $80$ 美元和 $8$ 美元，满足 $100$ 美元的预算。\n\n- 样例 2：你可以雇佣三个工人。你可以分别付给他们 $1$ 美元，$1.5$ 美元和 $1.5$ 美元。\n\n### 数据范围与约定\n\n对于任意测试点，如果你的方案满足了所有要求和你的目标，你将获得该测试点的满分。**否则**，如果你的第一行是正确的，即你输出了正确的工人数量 $H$，无论你接下来的输出是否符合格式，你都将获得该测试点 $50\\%$ 的分数。\n\n注意，在实际评测中，只有你的输出符合格式，才能获得测试点 $50\\%$ 或 $100\\%$ 的分数。\n\n- 对于 $50\\%$ 的数据，$N\\leq 5000$。\n- 对于 $100\\%$ 的数据，$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}$。\n\n注意，$W$ 超出了 $32$ 位整形变量的存储范围。你需要使用 $64$ 位整型变量存储 $W$，例如 C/C++ 中的 `long long` 或 Pascal 中的 `int64`。"}],"translated_statement":null,"sample_group":[["4 100\n5 1000\n10 100\n8 10\n20 1\n","2\n2\n3\n"],["3 4\n1 2\n1 3\n1 3\n","3\n1\n2\n3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}