[SCOI2015] 小凸玩密室

题目描述

小凸和小方相约玩密室逃脱,这个密室是一棵有 $n$ 个节点的完全二叉树,每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 $a_i$,每条边也有个权值 $b_i$。点亮第一个灯泡不需要花费,之后每点亮一个新的灯泡 $v$ 的花费,等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D_{u,v}$,乘以这个点的权值 $a_v$。在点灯的过程中,要保证任意时刻所有被点亮的灯泡必须连通,在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们,逃出密室的最少花费是多少。

输入输出格式

输入格式


第 $1$ 行包含 $1$ 个数 $n$,代表节点的个数 第 $2$ 行包含 $n$ 个数,代表每个节点的权值 $a_i$。 $(i = 1, 2,$……$, n)$ 第 $3$ 行包含 $n - 1$ 个数,代表每条边的权值 $b_i$,第 $i$ 号边是由第 $(i+1)/2$ 号点连向第 $i + 1$ 号点的边。$(i = 1, 2,$……$, n - 1)$

输出格式


输出包含 $1$ 个数,代表最少的花费。

输入输出样例

输入样例 #1

3
5 1 2
2 1

输出样例 #1

5

说明

对于 $10$% 的数据, $1 \leq n \leq 10$ 对于 $20$% 的数据, $1 \leq n \leq 20$ 对于 $30$% 的数据, $1 \leq n \leq 2000$ 对于 $100$% 的数据, $1 \leq n \leq 2 * 10^5, 1 \leq a_i, b_i \leq 10^5$