题目描述

在探险岛这款游戏中，有一个著名的山洞副本，里面有丰富的宝藏，吸引了许多勇者前来挑战。

不幸的是，山洞中有 N 个怪物，第 i 个怪物的防御力为 Ai，奖励值为 Bi。

M 个勇者依次前来挑战。假设一位勇者初始的战斗力为 X，当他的战斗力大于怪物的防御力 Ai 时，才可以击败它，并且获得奖励值 Bi 的战斗力提升。

幸运的是，每位勇者都深知自己的战斗力不一定充足，所以进入山洞后会在战斗前进行训练，来提升战斗力。并且勇者都很聪明，每位勇者都可以选择任意顺序来击败怪物，但一个怪物只能被击败一次。

具体来说：假设训练总天数为 n，勇者第 i 天的战斗力提升为 min(i,n-i+1) 。

因为勇者都希望自己能尽快穿越山洞，请你帮助每位勇者计算他最少训练多少天可以击败所有怪物？

你可以认为不同勇者之间是互相独立的，副本中的怪物会重新恢复状态。

输入描述

第一行 1 个正整数 N，表示怪物的数量。

第二行 N 个正整数 A1,A2,……,AN，即每个怪物的防御力。

第三行 N 个正整数 B1,B2,……,BN，即每个怪物的奖励值。

第四行 1 个正整数 M，表示有 M 个勇者前来挑战。

接下来 M 行，每行输入 1 个正整数 X，表示这名勇者的初始战斗力值。

输出描述

输出 1 行 M 个整数，表示每名勇者最少需要训练的天数。

3
4 8 2
1 1 1
3
1
5
4 

4 2 3 

3 
10 100 100
10 20 30
3
4
100
50 

18 0 12

数据范围

【样例说明】

样例 1 中，一共有 3 位勇者前来挑战。

• 第一位勇者锻炼4天，攻击力为1+1+2+2+1=7，然后可以击败所有怪物。

• 第二位勇者锻炼 2 天，攻击力为 5+1+1=7，可以击败所有怪物。

• 第三位勇者锻炼 3 天，攻击力为 4+1+2+1=8，可以击败所有怪物。

【数据范围】

对于 50%的数据，1≤N,M≤100,1≤X,Ai,Bi≤100 ；

对于 100%的数据，1≤N,M≤2×10^5，1≤X,Ai,Bi≤10^9；