Roofs
Description
During archaeological excavations, the ruins of an ancient temple were discovered. The colonnade, consisting of $n$ columns arranged in a row, has been preserved the best. All the columns have been partially destroyed, so it turned out that the heights of all the columns are different. The height of the $i$-th column is $h_i$.
To prevent further damage to the columns due to bad weather, it was decided to cover them with roofs. Each roof is placed horizontally and one end is attached to the top of a certain column. It is possible to install a roof that covers the segment of columns from the $i$-th to the $j$-th ($1 \leq i \leq j \leq n$) if one of the following conditions is met:
- If the $i$-th column is higher than all the others in the segment $[i, j]$, then the roof can be secured with its left end to the $i$-th column.
- If the $j$-th column is higher than all the others in the segment $[i, j]$, then the roof can be secured with its right end to the $j$-th column.
At the top of each column, no more than one roof can be attached. The cost of attaching a roof to the $i$-th column is $c_i$, regardless of whether it is directed to the left or to the right and how many columns it covers.
It is required to attach roofs to some columns in such a way that each column is covered by at least one roof, and the total cost is minimized.
The first line contains the number $n$ ($1 \le n \le 200\,000$) — the number of columns.
The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \leq h_i \leq 10^9$) — the heights of the columns. It is guaranteed that all $h_i$ are distinct.
The third line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the costs of attaching roofs to the columns.
Output a single number — the minimum cost to cover all the columns with roofs.
Input
The first line contains the number $n$ ($1 \le n \le 200\,000$) — the number of columns.
The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \leq h_i \leq 10^9$) — the heights of the columns. It is guaranteed that all $h_i$ are distinct.
The third line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the costs of attaching roofs to the columns.
Output
Output a single number — the minimum cost to cover all the columns with roofs.
3
3 10 7
2 5 2
1
5
2
7
2