小田喂猫

题目描述

小田买了 $n$ 种猫粮，第 $i$ 种猫粮的营养值为 $a_i$、数量为 $b_i$ 。

小田家的小猫名叫marble，它的饭量是无穷的，每天它都可以吃任意数量的猫粮，但是同一种猫粮它一天只会吃一次。

小田很疼爱marble，想把它喂得白白胖胖的，所以小田想知道在 $k$ 天内，marble可以获得的最大营养值之和是多少。

输入描述

第一行一个正整数 $n$，表示猫粮种数。

第二行输入 $n$ 个正整数 $a_{i}$，表示每种猫粮的营养值。

第三行输入 $n$ 个正整数 $b_i$，表示每种猫粮的数量。

第四行输入一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行输入一个正整数 $k$，表示询问天数。

输出描述

对于每次询问，在一行中输出一个整数表示答案。

输入输出样例

输入 #1

3
3 7 5
1 2 1
3
1
2
3

输出 #1

15
22
22

输入 #2

5
4 10 2 3 5
3 2 3 4 4
3
1
3
5

输出 #2

24
62
70

说明/提示

注意，每次询问都是独立计算的。

【样例 1 解释】

在 $1$ 天内，三种猫粮都吃一次，总营养为 $15$ 。

在 $2$ 天内，三种猫粮里，第一、三种可以吃一次，第二种吃两次，总营养为 $22$。

在 $3$ 天内，能吃的猫粮和 $2$ 天的没有差别，所以还是 $22$ 。

【数据范围】

对于 $50 \%$ 的数据，有 $n,q \le 10^{3}$。

对于所有测试数据，有：$1 \le n \le 10^{5}, 0 \le a_{i} \le 10^{4}, 1 \le b_{i} \le 10^{9}, 1 \le q \le 10^{5}, 1 \le k \le 10^{9}$ 。