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

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

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

例如下面的表达式：

现在小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} 。

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