Orange的闯关游戏

题目描述

Orange迷上了一款闯关游戏，游戏共有 $n$ 个关卡，每个关卡都有一个普通版本和一个特殊版本，首次通关每个关卡的特殊版本将会获得一把钥匙作为奖励（当且仅当第一次通关才会获得），只有通关了一个关卡的普通版本才能挑战这个关卡的特殊版本，而且根据游戏进度的限制，如果要挑战第 $i$ 个关卡的普通版本，必须保证前 $i - 1$ 个关卡的普通版本都至少被通关过一次，在游戏的最开始，你只能从第1关的普通版本开始挑战。

Orange通过第 $i$ 个关卡的普通版本需要花费代价 $p_i$ ，通过第 $i$ 个关卡的特殊版本需要花费代价 $q_i$ 。

现在，商店里刷新了 $T$ 件宝物，第 $i$ 件宝物需要 $w_i$ 把钥匙，你需要告诉Orange;每件宝物至少需要花费多少代价才能获得（每个问题均是独立的）。

输入格式

输入共包含 $T + 3$ 行，第一行包含2个整数 $n(n \leq 10^5)$ 和 $T(T \leq 100)$，第二行包含 $n$ 个整数 $p_i(p_i \leq 10^9)$，第三行包含 $n$ 个整数 $q_i(q_i \leq 10^9)$，随后包含 $T$ 行，每一行一个整数 $w_i (w_i \leq n)$ ，各个代数意义如上述题面所述。

输出格式

每行一个整数，表示Orange从第一关开始，要购买第 $i$ 件宝物需要花费的最小代价。

样例 #1

样例输入 #1

4 3
1 2 3 4
4 1 2 3
1
2
3

样例输出 #1

4
8
13

提示

对于样例1，显然先通关前两个普通关卡，再通关第二关的特殊关卡得到一把特殊钥匙，这是最优的。