Three displays

### 形式化题面 给定一个有两个性质 $s_i$ 和 $c_i$ 的数组，要求在其中选出三个数，满足： - $i<j<k$. - $s_i<s_j<s_k$. - $c_i+c_j+c_k$ 最小. ### 输入格式 第一行一个整数 $n$ 表示数组长度. 接下来一行 $n$ 个整数，表示 $s_i$. 接下来一行 $n$ 个整数，表示 $c_i$. ### 输出格式 一行一个整数，表示最小的 $c_i+c_j+c_k$ 翻译 @[zymooll](/user/289296)

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 < j < k $ that the font size increases if you move along the road in a particular direction. Namely, the condition $ s_i < s_j < 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.

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.

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 $ .

5
2 4 5 4 10
40 30 20 10 40

90

3
100 101 100
2 4 5

-1

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

33

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.