#2009. 「SCOI2015」小凸玩密室

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小凸和小方相约玩密室逃脱,这个密室是一棵有 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 号点的边。

输出格式

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

样例

样例输入

3
5 1 2
2 1

样例输出

5

数据范围与提示

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