Description

Xiao Tu and Xiao Fang decide to play an escape room. The escape room is a complete binary tree with $n$ nodes, and each node has a light bulb. You can escape by lighting all bulbs. Each bulb has a weight $a_i$, and each edge has a weight $b_i$. Lighting the first bulb costs nothing. After that, lighting a new bulb $v$ costs $D_{u,v} \times a_v$, where $u$ is the bulb lit immediately before and $D_{u,v}$ is the distance from $u$ to $v$ in the tree (the sum of edge weights along the path). During the process, at any time the lit bulbs must be connected. Moreover, once you light a bulb, you must finish lighting all bulbs in its subtree before you may light any bulb outside that subtree. Please tell them the minimum total cost to escape.

Input Format

The first line contains one integer $n$, the number of nodes.

The second line contains $n$ integers, the weight $a_i$ of each node ($i = 1, 2, \ldots, n$).

The third line contains $n - 1$ integers, the weight $b_i$ of each edge. The $i$-th edge connects node $\left\lfloor \dfrac{i+1}{2} \right\rfloor$ to node $i + 1$ ($i = 1, 2, \ldots, n - 1$).

Output Format

Output one integer, the minimum total cost.

3
5 1 2
2 1

5

Hint

For 10% of the testdata, $1 \leq n \leq 10$.

For 20% of the testdata, $1 \leq n \leq 20$.

For 30% of the testdata, $1 \leq n \leq 2000$.

For 100% of the testdata, $1 \leq n \leq 2 \times 10^5$, $1 \leq a_i, b_i \leq 10^5$.

Translated by ChatGPT 5