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.

Input

The first line contains a single integer n (3 ≤ n ≤ 3 000) — the number of displays.

The second line contains n integers s_1, s_2, …, s_n (1 ≤ s_i ≤ 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, …, c_n (1 ≤ c_i ≤ 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.

Examples

Input

5
2 4 5 4 10
40 30 20 10 40


Output

90


Input

3
100 101 100
2 4 5


Output

-1


Input

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


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.
mod = 1000000007
MOD = 998244353
ii = lambda :  int(input())
si = lambda :  input()
dgl = lambda : list(map(int, input()))
f = lambda :   map(int, input().split())
il = lambda :  list(map(int, input().split()))
it = lambda :  tuple(map(int, input().split()))
ls = lambda :  list(input())
n=ii()
l=il()
c=il()
mn=10**20
for i in range(1,n-1):
    lmn1=[c[j] for j in range(i) if l[j]<l[i]]
    lmn2=[c[j] for j in range(i+1,n) if l[j]>l[i]]
    if len(lmn1) and len(lmn2):
        mn=min(mn,min(lmn1)+min(lmn2)+c[i])
print(mn if mn!=10**20 else -1)