It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are $$$n$$$ displays placed along a road, and the $$$i$$$-th of them can display a text with font size $$$s_i$$$ only. Maria Stepanovna wants to rent such three displays with indices $$$i \lt j \lt k$$$ that the font size increases if you move along the road in a particular direction. Namely, the condition $$$s_i \lt s_j \lt s_k$$$ should be held.

The rent cost is for the $$$i$$$-th display is $$$c_i$$$. Please determine the smallest cost Maria Stepanovna should pay.

Input

The first line contains a single integer $$$n$$$ ($$$3 \le n \le 3\,000$$$) — the number of displays.

The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the font sizes on the displays in the order they stand along the road.

The third line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^8$$$) — the rent costs for each display.

Output

If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices $$$i \lt j \lt k$$$ such that $$$s_i \lt s_j \lt s_k$$$.

Note

In the first example you can, for example, choose displays $$$1$$$, $$$4$$$ and $$$5$$$, because $$$s_1 \lt s_4 \lt s_5$$$ ($$$2 \lt 4 \lt 10$$$), and the rent cost is $$$40 + 10 + 40 = 90$$$.

In the second example you can't select a valid triple of indices, so the answer is -1.

Three displays

Examples