自由泳

题目描述

高桥君可以用 $N$ 种泳姿游泳。

当他以第 $i$ 种泳姿游泳时，每秒消耗 $A_i$ 点体力，前进 $B_i$ 米。

回答 $Q$ 个查询。第 $i$ 个查询如下：

判断能否在总体力消耗不超过 $C_i$ 的前提下前进 $D_i$ 米。如果可能，求出所需的最少秒数。

这里，他可以自由组合不同的泳姿，切换泳姿所需的时间可以忽略不计。

具体来说，他可以按以下步骤游泳：

选择一个正整数 $m$、一个长度为 $m$ 的正实数序列 $t=(t_1,t_2,\dots,t_m)$ 和一个长度为 $m$ 的、每个元素都在 $1$ 到 $N$ 之间的整数序列 $x=(x_1,x_2,\dots,x_m)$。

然后，按照 $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$ 行输出答案，规则如下：

如果无法在总体力消耗不超过 $C_i$ 的前提下前进 $D_i$ 米，输出 -1。

否则，输出所需的最少时间。当输出值与正确答案的绝对误差或相对误差不超过 $10^{-9}$ 时，答案视为正确。

样例

4
1 2
2 3
3 3
4 4
5
4 7
7 7
49 100
1000 500
4 5

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

本输入中，高桥君可以用以下四种泳姿游泳：

每秒消耗 $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$ 秒，这是最短的。

数据范围

• 所有输入值均为整数
• $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$