1039: 冒险之路
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：7
解决：0
题目描述
在冒险岛这款游戏中，有一个著名的山洞副本，里面有丰富的宝藏，引来了许多勇者前来挑战。
不幸的是，山洞中有 $N$ 个怪物，第 $i$ 个怪物的防御力为 $A_i$ , 奖励值为 $B_i$ ， $M$ 个勇者依次前来挑战。
假设一位勇者初始的战斗力为 $X$ , 当你的战斗力**大于**怪物的防御力 $A_i$ 时，你才可以击败它，并且获得奖励值 $B_i$ 的战斗力提升。
因为勇者都希望自己能尽快穿越山洞，请你帮助每位勇者计算他**最少**训练多少天可以击败所有怪物？
你可以认为不同的勇者之间是**互相独立**的，副本中的怪物会重新恢复状态。
不幸的是，山洞中有 $N$ 个怪物，第 $i$ 个怪物的防御力为 $A_i$ , 奖励值为 $B_i$ ， $M$ 个勇者依次前来挑战。
假设一位勇者初始的战斗力为 $X$ , 当你的战斗力**大于**怪物的防御力 $A_i$ 时，你才可以击败它，并且获得奖励值 $B_i$ 的战斗力提升。
幸运的是，每位勇者都深知自己的战斗力不一定充足,所以他会在进入山洞战斗前进行训练,依次来提升他的战斗力，并且勇者都是很聪明的，每位勇者都可以选择**任意顺序**来击败怪物,一个怪物只能被击败一次。
因为勇者都希望自己能尽快穿越山洞，请你帮助每位勇者计算他**最少**训练多少天可以击败所有怪物？
你可以认为不同的勇者之间是**互相独立**的，副本中的怪物会重新恢复状态。
输入
第一行 $1$ 个正整数 $N$ , 表示怪物的数量
第二行 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。即每个怪物的防御力
第三行 $N$ 个正整数 $B_1, B_2, \ldots, B_N$。即每个怪物的奖励值
第四行 $1$ 个正整数 $M$ , 表示有 $M$ 个勇者前来挑战
接下来 $M$ 行，每行输入 $1$ 个正整数 $X$ , 表示这名勇者的初始战斗力值
第二行 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。即每个怪物的防御力
第三行 $N$ 个正整数 $B_1, B_2, \ldots, B_N$。即每个怪物的奖励值
第四行 $1$ 个正整数 $M$ , 表示有 $M$ 个勇者前来挑战
接下来 $M$ 行，每行输入 $1$ 个正整数 $X$ , 表示这名勇者的初始战斗力值
输出
输出 $1$ 行 $M$ 个整数，表示每名勇者最少需要训练的天数。
样例输入 复制
3
4 8 2
1 1 1
3
1
5
4样例输出 复制
4 2 3提示
### **样例说明**
第一组样例中，一共有 $3$ 位勇者前来挑战。
- 第一位勇者锻炼 $4$ 天 , 攻击力为 $1+1+2+2+1=7 $ ，然后可以击败所有怪物
- 第二位勇者锻炼 $2$ 天 , 攻击力为 $5+1+1=7 $ ，可以击败所有怪物
- 第三位勇者锻炼 $3$ 天 , 攻击力为 $4+1+2+1=8 $ ，可以击败所有怪物
### **数据范围**
- 对于 $30\%$ 的数据，$1\le \ N , M \le 100$ , $ 1\ \leq\ X,A_i,B_i\ \leq\ 100$
- 对于 $100\%$ 的数据，$ 1\ \le\ N,M\ \leq\ 2\ \times\ 10^5 $ , $ 1\ \leq\ X,A_i,B_i\ \leq\ 10^9 $
第一组样例中，一共有 $3$ 位勇者前来挑战。
- 第一位勇者锻炼 $4$ 天 , 攻击力为 $1+1+2+2+1=7 $ ，然后可以击败所有怪物
- 第二位勇者锻炼 $2$ 天 , 攻击力为 $5+1+1=7 $ ，可以击败所有怪物
- 第三位勇者锻炼 $3$ 天 , 攻击力为 $4+1+2+1=8 $ ，可以击败所有怪物
### **数据范围**
- 对于 $30\%$ 的数据，$1\le \ N , M \le 100$ , $ 1\ \leq\ X,A_i,B_i\ \leq\ 100$
- 对于 $100\%$ 的数据，$ 1\ \le\ N,M\ \leq\ 2\ \times\ 10^5 $ , $ 1\ \leq\ X,A_i,B_i\ \leq\ 10^9 $