Problem Description

fyj 在《丝之歌》中屡次被 Boss「残暴的兽蝇」暴打，而且这种兽蝇有很多只，每只都有不同的属性。fyj 觉得是自己攻击力不够，于是为了变强，他找到了跳蚤旅团团长 穆什卡。

穆什卡承诺：只要 fyj 在小游戏「跳蚤耍耍」里拿到足够分数，就能兑换一瓶特调版跳蚤蜜酿。喝下特调版跳蚤蜜酿后，fyj 在之后对战中每回合造成的伤害将固定等于该局小游戏获得的分数。也就是说，如果该局小游戏的分数为 $x$，那么特调版跳蚤蜜酿可以把 fyj 的攻击力变为 $x$。

「跳蚤耍耍」有 $m$ 种不同的关卡，但游玩关卡需要花费念珠(《丝之歌》的货币单位)；不同关卡能获得不同分数。

由于fyj打了一天兽蝇都打不过，非常的疲惫，所以请你帮帮可怜的fyj解决下面的问题吧：

对每个询问给定一个整数 $A$（表示 fyj 需要的固定攻击力/分数），你需要计算，在遵守穆什卡规则的前提下，获得恰好 $A$ 分所需的最少念珠数。

---

得分方式与规则

共有 $m$ 种关卡。游玩第 $i$ 种关卡：

支付 $b_i$ 枚念珠，可以获得 $a_i$ 分。

穆什卡规定：

规则 1（基础补得） 任意时刻都可以支付 $1$ 枚念珠直接获得 $1$ 分。（即 $1$ 念珠 $\leftrightarrow 1$ 分）

规则 2（单关卡限制） 每次游戏（每次询问）只能选择一个关卡类型反复游玩。你不能在一次游戏中同时游玩两个或以上不同关卡。 如果反复游玩该关卡后分数仍不足 $A$，剩余部分只能用规则 1 补齐。

更形式化地说：你可以选择一个关卡 $i$，并游玩它 $k$ 次（$k$ 为非负整数），然后用基础补得补齐剩余分数。最终分数必须恰好为 $A$。

Input Format

• 第一行一个整数 $m$，表示关卡数量。
• 接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示游玩第 $i$ 种关卡可得 $a_i$ 分，花费 $b_i$ 念珠。
• 下一行一个整数 $q$，表示询问数量。
• 接下来 $q$ 行，每行一个整数 $A$，表示目标分数（也等同于所需固定攻击力）。

Output Format

对每个询问输出一行一个整数：获得恰好 $A$ 分所需的最少念珠数。

Sample

输入：

2
7 3
10 5
1
63

输出：

27

解释：选择关卡 $(a,b)=(7,3)$ 游玩 $9$ 次得到 $63$ 分，花费 $27$ 念珠，且无需基础补得，为最优。

Hint

$$1 \le m \le 5\times 10^4$$ $$1 \le a_i \le 5\times 10^5$$ $$0 \le b_i \le a_i$$ $$1 \le q \le 5\times 10^4$$ $$\text{对每个询问计算得到的最小攻击力 } A \le 5\times 10^5$$