该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 D 在看到小 C 脑洞打开定义的加乘运算后，也脑袋一拍，定义了乘加运算！

他定义 $a *^bc=(a+b)\times c$ 。

而且他觉得用括号来规定运算的先后顺序太麻烦了，他给乘加运算定义了一个权值的系数（为乘加运算的下标），权值大的乘加运算先进行。

例如下面的表达式：

$$\begin{aligned} &9\ *^4_3\ 9\ *^2_1\ 1\ *^3_2\ 6\ *^1_4\ 2\\ =&9\ *^4_3\ 9\ *^2_1\ 1\ *^3_2\ (6+1)\times 2 \ \ \ \ \text{因为}*^1_4\text{权值最大(4)，所以先运算} \\ =&(9+4)\times 9\ *^2_1\ 1\ *^3_2\ 14\\ =&117\ *^2_1\ (1+3)\times14\\ =&(117+2)\times56\\ =&6664 \end{aligned} $$

现在小D 给你一个只含有乘加运算的表达式，希望你能帮他求出最后的值。

输入格式

第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数，分别为 $a_1,a_2,...,a_n$ 。

第三行包含 $n-1$ 个整数，分别为 $b_1,b_2,...,b_{n-1}$ 。

第四行包含 $n-1$ 个整数，分别为 $c_1,c_2,...,c_{n-1}$ ，保证 $c_i$ 互不相同。

最后表达式就是：$a_1*^{b_1}_{c_1}a_2*^{b_2}_{c_2}...*^{b_{n-1}}_{c_{n-1}}a_n$ 。

输出格式

输出一行一个整数，表示表达式的值，保证其绝对值小于等于 $10^{18}$ 。

样例

输入

5
9 9 1 6 2
4 2 3 1
3 1 2 4

输出

6664

数据范围

对于 $100\%$ 的数据，保证：$1 \leq n\le 10^5,0\le a_i,c_i\le 10^9,-10^9\le b_i\le 10^9$。

测试点编号	数据范围	特殊性质
$1\sim 3$	$n\le 100$	无
$4\sim 8$	$n\le 1000$
$9$	无限制	$a_i=0$
$10\sim 14$		$b_i=0$
$15\sim 20$		无