题目描述

在《小杨的奇幻冒险》这款游戏中，有一个神秘的魔法森林副本，里面藏满了珍贵的魔法水晶，吸引了很多冒险者前来挑战。

不过，这个森林里有 N 个强大的魔法守护兽，第 i 个守护兽的防御力为 Ai​，击败它后可以获得奖励值为 Bi​ 的魔法能量提升。为了拯救被黑暗势力困住的公主，小杨决定挑战这个魔法森林。

假设小杨初始的战斗力为 $X$ , 当小杨的战斗力大于守护兽的防御力 $A_i$ 时，小杨才可以击败它，并且获得奖励值 $B_i$ 的战斗力提升。

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

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

具体来说，假设小杨训练了 n 天，那么他每天可以获得的魔法能量提升为 min(i,n−i+1)，其中 i 表示训练的第几天。

因为小杨希望通过最少的训练天数通关，所以请你帮他计算一下，他最少需要训练多少天才能击败所有守护兽。

输入格式

第一行 1 个正整数 N，表示守护兽的数量。

第二行 N 个正整数$A _1,A_2,…,A_N​$。即每个守护兽的防御力。

第三行 N 个正整数 $B _1,B_2,…,B_N​$。即每个守护兽的奖励值。

第四行 1 个正整数 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

提示

样例说明

第一组样例中，小杨尝试了 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$