AT_abc356_g [ABC356G] Freestyle

高桥可以游出 $N$ 种不同的风格。 当他用第 $i$ 式游泳时，每秒消耗 $A_i$ 体力，每秒前进 $B_i$ 米。 回答 $Q$ 个问题。 第 $i$ 次查询如下： - 判断是否有可能在总体力消耗不超过 $C_i$ 的情况下前进 $D_i$ 米。如果可能，请找出所需的最少秒数。 在这里，他可以自由组合不同的泳姿，切换泳姿的时间可以忽略不计。 具体来说，他可以使用以下步骤游泳： - 选择一个正整数 $m$ ，一个长度为 $m$ 的正实数序列 $t=(t_1,t_2,\dots,t_m)$ ，以及一个长度为 $m$ 的整数序列 $x=(x_1,x_2,\dots,x_m)$ ，其中每个元素都介于 $1$ 和 $N$ 之间（含）。 - 然后，按照 $i=1,2,\dots,m$ 的顺序，以第 $x_i$ 的方式游 $t_i$ 秒。

输入内容由标准输入法提供，格式如下 >$N$ > >$A_1$ $B_1$ > >$A_2$ $B_2$ > >$\vdots$ > >$A_N$ $B_N$ > >$Q$ > >$C_1$ $D_1$ > >$C_2$ $D_2$ > >$\vdots$ > >$C_Q$ $D_Q$

共输出 $Q$ 行。 对于第 $i$ 次查询，在第 $i$ 行输出答案如下： - 如果不可能前进 $D_i$ 米，同时保持体力消耗总量不超过 $C_i$ ，则输出 `-1`。 - 否则，输出所需的最短时间。如果输出值与真实答案之间的绝对或相对误差不超过 $10^{-9}$ ，则认为输出正确。

#### 限制因素 - 所有输入值均为整数。 - $1 \le N \le 2 \times 10^5$ - $1 \le A_i, B_i \le 10^9$ - $1 \le Q \le 2 \times 10^5$ - $1 \le C_i, D_i \le 10^9$ #### 样例 $1$ 说明 在此输入中，高桥可以用以下四种方式游泳： - 消耗 $1$ 体力，每秒前进 $2$ 米。 - 消耗 $2$ 体力，每秒前进 $3$ 米。 - 消耗 $3$ 体力，每秒前进 $3$ 米。 - 消耗 $4$ 体力，每秒前进 $4$ 米。 此输入包含五个查询。 - 第一个查询，$C_1=4, D_1=7$ 。 - 选择 $t=(1,2)$ 和 $x=(2,1)$ 。高桥游泳的过程如下： - 在前 $1$ 秒，他消耗了 $2$ 体力，前进了 $3$ 米。 - 接下来的 $2$ 秒，他消耗了 $2$ 体力，前进了 $4$ 米。 - 他总共消耗了 $4$ 体力，前进了 $7$ 米。所需的时间为 $3$ 秒，这是最小值。 - 第二个查询，$C_2=7, D_2=7$ 。 - 选择 $t=(7/4)$ 和 $x=(4)$ 。高桥游程如下： - 在最初的 $7/4$ 秒内，他消耗了 $7$ 体力，前进了 $7$ 米。 - 他总共消耗了 $7$ 体力，前进了 $7$ 米。所需的时间为 $7/4$ 秒，这是最小值。 - 第三个查询，$C_3=49, D_3=100$ 。 - 无论高桥如何游泳，都不可能在总体力消耗不超过 $49$ 的情况下前进 $100$ 米。 - 第四个查询， $C_4=1000, D_4=500$ 。 - 选择 $t=(125)$ 和 $x=(4)$ 。高桥游泳的情况如下： - 在前 $125$ 秒，他消耗了 $500$ 体力，前进了 $500$ 米。 - 他总共消耗了 $500$ 体力，前进了 $500$ 米。所需的时间为 $125$ 秒，这是最小值。 - 第五个查询， $C_5=4, D_5=5$ 。 - 选择 $t=(1/2,1)$ 和 $x=(4,2)$ 。高桥游程如下： - 在前 $1/2$ 秒，他消耗了 $2$ 体力，前进了 $2$ 米。 - 在接下来的 $1$ 秒内，他消耗了 $2$ 点体力，前进了 $3$ 米。 - 他总共消耗了 $4$ 体力，前进了 $5$ 米。所需的时间为 $3/2$ 秒，这是最短时间。