P9113 [IOI 2009] Hiring

IOI2009 D1T2

你需要为一个建设项目雇佣一些工人。现在有 $N$ 位候选工人，标号为 $1\sim N$。第 $k$ 个工人要求如果自己被雇佣，则必须得到至少 $S_k$ 美元的工资。每个工人有能力值 $Q_k$。建筑业监管局规定，你必须按工人们的能力值的比例分配他们的工资。例如，如果 $Q_A = 3Q_B$，则你付给 $A$ 的工资必须恰为 $B$ 的三倍。你可以付给你的工人们任意非负实数金额的工资。 你的手上有 $W$ 美元，你想用这些钱雇佣最大数量的工人。你可以决定选用哪些工人以及付给他们的工资，但必须满足每个工人的最低工资要求以及监管局的分配规定，并保证工资总额不超过 $W$。 工人们的能力值和你的项目无关，因此你只想最大化雇佣工人的数量，而不关心他们的能力值。尽管如此，你仍希望最小化你的支出，即如果存在多种方案，则你需要选择支付给工人们的工资总额最小的那一个。如果仍存在多种方案，任意一个都是满足要求的。 **任务**：编写一个程序，给定每个工人的工资要求和能力值，以及你拥有的资金，计算出具体雇佣哪些工人。你必须在最大化工人的数量的前提下最小化支出，并满足上文提到的监管局的要求。

第一行包含两个由空格隔开的整数 $N, W$，分别表示候选工人数和你拥有的资金。 接下来 $N$ 行，每行描述一个候选工人。其中第 $k$ 行描述第 $k$ 个候选工人，包含两个由空格隔开的整数 $S_k, Q_k$。

第一行一个整数 $H$，表示你雇佣的工人数量。 接下来 $H$ 行，每行一个整数，表示你雇佣的所有工人的编号（互不相同），以任意顺序排列。

### 样例解释 - 样例 1：选择工人 $2$ 和 $3$ 是唯一符合所有要求且雇佣了两个工人的方案。你可以分别付给他们 $80$ 美元和 $8$ 美元，满足 $100$ 美元的预算。 - 样例 2：你可以雇佣三个工人。你可以分别付给他们 $1$ 美元，$1.5$ 美元和 $1.5$ 美元。 ### 数据范围与约定 对于任意测试点，如果你的方案满足了所有要求和你的目标，你将获得该测试点的满分。**否则**，如果你的第一行是正确的，即你输出了正确的工人数量 $H$，无论你接下来的输出是否符合格式，你都将获得该测试点 $50\%$ 的分数。 注意，在实际评测中，只有你的输出符合格式，才能获得测试点 $50\%$ 或 $100\%$ 的分数。 - 对于 $50\%$ 的数据，$N\leq 5000$。 - 对于 $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}$。 注意，$W$ 超出了 $32$ 位整形变量的存储范围。你需要使用 $64$ 位整型变量存储 $W$，例如 C/C++ 中的 `long long` 或 Pascal 中的 `int64`。