You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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