题目描述

No.777 谜拟Q (ミミッキュ)

属性:幽灵/妖精
特性:画皮(ばけのかわ),通过画皮覆盖住身体,可以防住1次攻击。

经过了两年,CC成长了许多,带着他的谜拟Q来到了更大、更强的道馆。
现在CC要挑战$n$名训练师,其中挑战第$i$($1 \leq i \leq n$)名训练师需要花费$a_i$点HP值,同时,战胜该名训练师后将会获得一个可以回复$b_i$点HP值的回复药。

以下几点需要注意:

  • CC的谜拟Q的HP值在任何时候都不能小于等于$0$(否则就需要从头开始挑战了);
  • CC的谜拟Q比较handsome,所以没有HP值上限限制(即HP值可为大于$0$的任意整数);
  • 每名训练师至多只能被挑战一次;
  • CC可以以任意顺序挑战这$n$名训练师;
  • CC不一定要挑战完所有训练师。

现在CC想知道的是,每次给出谜拟Q的初始HP值$c$,CC最多能战胜多少名训练师。


输入格式

首先一行一个整数$n$($1 \leq n \leq 1000$),表示训练师数量。

接下来$n$行,每行两个整数$a_i$,$b_i$($0 \leq a_i$,$b_i \leq 10^9$),表示挑战第$i$名训练师需要花费$a_i$点HP值,战胜后将会获得一个可以回复$b_i$点HP值的回复药。

之后是一个整数$T$($1 \leq T \leq 1000$),表示CC问的问题数量。

接下来$T$行每行一个整数$c_i$($1 \leq c_i \leq 10^9$),表示在CC的第$i$个询问中,谜拟Q的初始HP值为$c_i$。


输出格式

输出共$T$行,一行一个整数,在每个询问给出的初始HP值下,CC最多能战胜多少名训练师。


样例数据

输入

5
3 2
2 2
0 1
4 4
6 10
6
1
2
3
4
5
6

输出

1
2
3
4
4
5

备注

对于初始HP为$5$的询问,一个可行的挑战顺序为:$(3,2) \rightarrow (0,1) \rightarrow (2,2) \rightarrow (4,4)$,最终共战胜$4$个训练师,谜拟Q的最终HP值为$5$。


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务