Farm Village

Time limit2sMemory limit512 MB

Summary

Each house along a road needs one crop unit and can grow up to two; minimize the total growing cost plus cost of carrying crops between neighbors.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

There is a village along a road. The village has $N$ houses, numbered 1 to $N$ in order along the road. Each house has a field that can grow up to two units of the crop, and each house needs exactly one unit. The total cost of giving every house one unit of the crop is the sum of the carrying costs and the growing costs.

Carrying cost: carrying one unit of the crop between house $i$ and house $i+1$ costs $d_i$ . The cost is the same in either direction.
Growing cost: growing one unit of the crop in the field of house $i$ costs $g_i$ .

Compute the minimum total cost of supplying one unit of the crop to every house.

Input

The input is a single test case in the following format.

N
d1 d2 ... dN-1
g1 g2 ... gN

The first line contains an integer $N$ ( $2 \le N \le 200{,}000$ ), the number of houses. The second line contains $N-1$ integers separated by spaces. The $i$ -th integer $d_i$ ( $1 \le d_i \le 10^9$ , $1 \le i \le N-1$ ) is the carrying cost between house $i$ and house $i+1$ . The third line contains $N$ integers separated by spaces. The $i$ -th integer $g_i$ ( $1 \le g_i \le 10^9$ , $1 \le i \le N$ ) is the growing cost of the field of house $i$ .

Output

Print the minimum cost of supplying one unit of the crop to every house.

Examples3

Example 1
Input
```
2
3
1 5
```
Expected output
```
5
```
Example 2
Input
```
3
100 100
1 2 3
```
Expected output
```
6
```
Example 3
Input
```
4
1 2 3
1 1 100 100
```
Expected output
```
12
```