Cutting down trees

Time limit2sMemory limit512 MB

Summary

Cut every tree to height 0; each recharge costs b_i where i is the largest index already felled, and you must minimize total cost given increasing a_i and decreasing b_i.

Level: Medium7 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

There are $n$ trees with heights $a_1, a_2, \dots, a_n$ , and you want to cut every one of them down with a chainsaw.

Each time you use the chainsaw on tree $i$ , the height of that tree drops by 1. The chainsaw has to be recharged after every use, and the price of one recharge depends on the largest index among the trees whose height already reached 0. If that index is $i$ , one recharge costs $b_i$ . While no tree has height 0, the chainsaw cannot be recharged. The chainsaw is charged at the very start.

Given the heights $a_i$ and the recharge cost $b_i$ of each tree, write a program that computes the minimum total recharge cost needed to bring every tree down to height 0.

Input

The first line contains $n$ ( $1 \le n \le 100\,000$ ). The second line contains $a_1, a_2, \dots, a_n$ and the third line contains $b_1, b_2, \dots, b_n$ . ( $1 \le a_i \le 10^9$ , $0 \le b_i \le 10^9$ )

The input satisfies $a_1 = 1$ , $b_n = 0$ , $a_1 < a_2 < \dots < a_n$ , and $b_1 > b_2 > \dots > b_n$ .

Output

Print the minimum total recharge cost needed to cut down every tree.

Examples2

Example 1
Input
```
5
1 2 3 4 5
5 4 3 2 0
```
Expected output
```
25
```
Example 2
Input
```
6
1 2 3 10 20 30
6 5 4 3 2 0
```
Expected output
```
138
```