题目描述

小凸和小方相约玩密室逃脱，这个密室是一棵有 $ n $ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 $ A_i $，每条边也有个权值 $ b_i $。

点亮第 $ 1 $ 个灯泡不需要花费，之后每点亮一个新的灯泡 $ V $ 的花费，等于上一个被点亮的灯泡 $ U $ 到这个点 $ V $ 的距离 $ D(u, v) $，乘以这个点的权值 $ A_v $。

在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。

输入格式

第一行包含一个数 $ n $，代表节点的个数。
第二行包含 $ n $ 个数，代表每个节点的权值 $ a_i $。
第三行包含 $ n - 1 $ 个数，代表每条边的权值 $ b_i $，第 $ i $ 号边是由第 $ \frac{i + 1}{2} $ 号点连向第 $ i + 1 $ 号点的边。

输出格式

输出包含一个数，代表最少的花费。

样例

input

3
5 1 2
2 1

output

5

数据范围与提示

$ 1 \leq N \leq 2 \times 10 ^ 5, 1 < A_i, B_i \leq 10 ^ 5 $