题目描述

“走过路过不要错过！史上最优惠金坷垃！快来抢购！”

商店里正在出售各种不同口味的金坷垃，有草莓味、香草味、巧克力味……第 i 袋金坷垃的价格为 p_i，美味度为 v_i。

小珅非常喜欢金坷垃，但是他也很喜欢银坷垃，所以他每次能够拿出来购买金坷垃的钱并不确定。每当小珅变卦一次，你都需要迅速回答：在不超过当前预算的前提下，最多可以买到多少美味度。

输入格式

第一行，一个整数 N（1≤N≤100）。

第二行，N 个整数 p1，p2，…，pN（1≤p_i≤5000），表示每袋金坷垃的价格。

第三行，N 个整数 v1，v2，…，vN（1≤v_i≤10000），表示每袋金坷垃的美味度。

第四行，一个整数 Q（1≤Q≤100000），表示小珅变卦的次数。

接下来 Q 行，每行一个整数 M（1≤M≤5000），表示本次购买的预算。

输出格式

对于每次变卦，输出一行一个整数，表示在当前预算下能够买到的最大美味度。

输入样例 #1

3
3 1 4
7 9 8
3
3
4
1

输出样例 #1

9
16
9

输入样例 #2

3
6 4 10
6 20 6
3
4
6
2

输出样例 #2

20
20
0

输入样例 #3

1
2
7
3
1
2
5

输出样例 #3

0
7
7

数据范围与约定

1≤N≤100，1≤p_i≤5000，1≤v_i≤10000，1≤Q≤100000，1≤M≤5000