SP27039 EIUASSEMBLY - Assembly line

ACM 工厂有一个很大的制造产品的流水线。一共有 $N$ 个机器人在流水线上工作，第 $i$ 个机器人做每个产品的第 $i$ 个步骤，工作效率为 $P_i$ 个每小时。 工厂现在得到了一笔 $M$ 马内的预算来提高流水线的生产效率。已知每花 $M_i$ 马内可以第 $i$ 个机器人的生产效率 $P_i$ 提高 $1$ 个每小时，请问怎样分配才能使流水线的生产效率最高？

**本题有多组数据。** 输入第 $1$ 行包含一个数 $T$，表示有 $T$ 组测试数据。 接下来每组数据格式如下： - 每组数据的第 $1$ 行包含两个整数 $N,M$，表示机器人的数量与预算的钱数。 - 接下来 $N$ 行，每行包含两个整数 $P_i,M_i$，表示第 $i$ 个机器人的初始工作效率与提高工作效率所需要的钱数。

一个整数，表示在花最多 $M$ 马内的情况下流水线每小时可以生产的产品数。

$1 \le T \le 10$ $1 \le N \le 10^5$ $0 \le M \le 10^{12}$ $1 \le P_i,M_i \le 10^9$ --- Translated by @[chuxuanzhe](/user/552298) 2022/7/19