Three displays

Description:

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 < j < k$$$ such that $$$s_i < s_j < s_k$$$.

Sample Input:

5
2 4 5 4 10
40 30 20 10 40

Sample Output:

90

Sample Input:

3
100 101 100
2 4 5

Sample Output:

-1

Sample Input:

10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

Sample Output:

33

Note:

In the first example you can, for example, choose displays $$$1$$$, $$$4$$$ and $$$5$$$, because $$$s_1 < s_4 < s_5$$$ ($$$2 < 4 < 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.