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


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

Difficulty: interview

Starter code:

Solutions:
from math import inf
n=int(input())

a = input()
a= [int(i) for i in a.split()]
s  =input()
s  = [int(i) for i in s.split()]
ans  =  inf
for j in range(1 , n-1):
    ll , lr = inf , inf
    for q in range(j+1,n):
        if a[j]<a[q]:
            lr = min(lr , s[q])
    for q in range(j):
        if a[j]>a[q]:
            ll = min(ll , s[q]) 
    ans= min(ans , ll+lr+s[j])
if ans==inf:
    print(-1)
else:
    print(ans)


from math import inf
n = int(input())
s = [int(e) for e in input().split()]
c = [int(e) for e in input().split()]
d = [[inf, inf] for i in range(n)]
for i in range(n):
    s1 = s[i]
    for j in range(i):
        if s[j] < s1:
            if c[j] < d[i][0]:
                d[i][0] = c[j]
            if d[j][0] < d[i][1]:
                d[i][1] = d[j][0]
    d[i][0] += c[i]
    d[i][1] += c[i]
m = min([e[1] for e in d])
print(m if m < inf else -1)

n=int(input())
l=list(map(int,input().split()))
v=list(map(int,input().split()))
d=dict()
for i in range(n):
    take=[]
    for j in range(i+1,n):
        if l[i]<l[j]:
            take.append(v[j])
    
    d[i]=sorted(take)
mini=99999999999
for i in range(n):
    sum1=v[i]
    for j in range(i+1,n):
        if l[i]<l[j]:
            sum1=v[j]+v[i]
            if len(d[j])!=0:
                sum1=v[i]+v[j]+d[j][0]
                if mini>sum1:
                    mini=sum1
if mini==99999999999:
    print("-1")
else:
    print(mini)
            


n = int(input())
s = list(map(int, input().split()))
c = list(map(int, input().split()))
num = float("inf")
rec1 = [float("inf")] * n
rec2 = [float("inf")] * n
for i in range(n):
    for j in range(i + 1, n):
        if s[i] < s[j] and rec1[i] > c[j]:
            rec1[i] = c[j]

for i in range(1, n):
    for j in range(i):
        if s[j] < s[i] and rec2[i] > c[j]:
            rec2[i] = c[j]

for i in range(n):
    num = min(num, rec1[i] + c[i] + rec2[i])


if num == float("inf"):
    print(-1)
else:
    print(num)

n = int(input())
a = list(map(int, input().split()))
c = list(map(int, input().split()))
MAXANS = 300000010
f = {
	1:[c[i] for i in range(n)],
	2:[MAXANS for _ in range(n)],
	3:[MAXANS for _ in range(n)]
	}
v = [False for _ in range(n)]
l = 2
for i in range(n - 1):
	if v[i]:
		continue
	for j in range(i + 1, n):
		if (a[j] > a[i]) and (c[j] > c[i]):
			v[j] = True
		if (a[i] < a[j]) and (f[l-1][i] + c[j] < f[l][j]):
				f[l][j] = f[l-1][i] + c[j]
l = 3
for i in range(n - 1):
	if f[2][i] == MAXANS:
		continue
	for j in range(i + 1, n):
		if (a[i] < a[j]) and (f[l-1][i] + c[j] < f[l][j]):
				f[l][j] = f[l-1][i] + c[j]

ans = min(f[3])
if ans == MAXANS:
	print(-1)
else:
	print(ans)



import sys
from collections import deque

n = int(sys.stdin.readline().strip())
s = list(map(int, sys.stdin.readline().strip().split(' ')))
c = list(map(int, sys.stdin.readline().strip().split(' ')))

lower = [float('inf') for i in range(n)]
upper = [float('inf') for i in range(n)]
for i in range(n):
	for j in range(i):
		if s[i] > s[j]:
			lower[i] = min(lower[i], c[j])
for i in range(n-1,-1,-1):
	for j in range(i+1,n):
		if s[j] > s[i]:
			upper[i] = min(upper[i], c[j])
ans = float('inf')
for i in range(n):
	ans = min(ans, lower[i] + c[i] + upper[i])
print([-1,ans][ans!=float('inf')])

n = int(input())
s = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
f1 = [0 for x in range(0,3005)]
f = [[99999999999 for x in range(0,3005)] for i in range(1,4)]
f.insert(0,f1)
for i in range(0,n):
    f[1][i] = c[i]
for x in range(2,4):
    for i in range(x-1,n):
        for j in range(0,i):
            if s[j] < s[i] and f[x-1][j] != 99999999999:
                f[x][i] = min(f[x-1][j]+c[i], f[x][i])
for i in range(1,n):
    f[3][i] = min(f[3][i-1],f[3][i])
if f[x][i] != 99999999999:
    print(f[x][i])
else:
    print(-1)

R=lambda:list(map(int,input().split()))
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(1,n-1))
print((r,-1)[r>I])

R=lambda:list(map(int,input().split()))
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])

n = int(input())
S = [int(x) for x in input().split()]
s = tuple(S)
c = tuple(int(x) for x in input().split())
S.sort()
def min(x, y):
    if x < y:
        return x
    else:
        return y
def rank(x):
    l = 0; r = n - 1
    while l < r:
        mid = (l + r) >> 1
        if S[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l
rk = tuple(rank(x) for x in s)
Min = [10000000000 for i in range(30000)]
def insert(x, l, r, p, v):
    Min[x] = min(Min[x], v)
    if l == r:
        return
    mid = (l + r) >> 1
    if p > mid:
        insert(x << 1 | 1, mid + 1, r, p, v)
    else:
        insert(x << 1, l, mid, p, v)
def query(x, l ,r ,L ,R):
    if l >= L and r <= R:
        return Min[x]
    mid = (l + r) >> 1; ans = 10000000000
    if L <= mid:
        ans = min(ans, query(x << 1, l, mid, L, R))
    if R > mid:
        ans = min(ans, query(x << 1 | 1, mid + 1, r, L, R))
    return ans
dp = list(c)
Min = [10000000000 for i in range(30000)]
for i in range(0, n):
    insert(1, 0, n - 1, rk[i], dp[i])
    dp[i] = c[i]
    if rk[i] == 0:
        dp[i] += 10000000000
    else:
        dp[i] += query(1, 0, n - 1, 0, rk[i] - 1)
Min = [10000000000 for i in range(30000)]
for i in range(0, n):
    insert(1, 0, n - 1, rk[i], dp[i])
    dp[i] = c[i]
    if rk[i] == 0:
        dp[i] += 10000000000
    else:
        dp[i] += query(1, 0, n - 1, 0, rk[i] - 1)
ans = 10000000000
for i in dp:
    ans = min(ans, i)
if ans > 3000000000:
    print(-1)
else:
    print(ans)

R=lambda:list(map(int,input().split()))
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])


#R=lambda:list(map(int,input().split()))
R=lambda:[int(i)for i in input().split()]
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])


import math;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n=int(input());
s=getIntList();
c=getIntList();
maxValue=10**8+1;
result=maxValue*3;
minLeft=[0]*n;
minRight=[0]*n;
minLeft[0]=c[0];
for i in range(1, n):
    minLeft[i]=min(c[i], minLeft[i-1]);
minRight[n-1]=c[n-1];
for i in range(n-2, -1, -1):
    minRight[i]=min(c[i], minRight[i+1]);
minSLeft=[0]*n;
maxSRight=[0]*n;
minSLeft[0]=s[0];
for i in range(1, n):
    minSLeft[i]=min(s[i], minSLeft[i-1]);
maxSRight[n-1]=s[n-1];
for i in range(n-2, -1, -1):
    maxSRight[i]=max(s[i], maxSRight[i+1]);
prices=[(c[j], j) for j in range(1, n-1)];
prices.sort();
for currC, j in prices:
    if minLeft[j-1]+c[j]+minRight[j+1]>=result:
        continue;
    if minSLeft[j-1]>=s[j] or s[j]>=maxSRight[j+1]:
        continue;
    a=maxValue;
    for i in range(j):
        if s[i]<s[j]:
            a=min(a, c[i]); 
    b=maxValue;
    for k in range(j+1, n):
        if (s[j]<s[k]):
            b=min(b, c[k]);
    curr=a+b+c[j];
    result=min(result, curr);
if result==maxValue*3:
    result=-1;
print(result);


#R=lambda:list(map(int,input().split()))
"""
R=lambda:[int(i)for i in input().split()]
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])
"""
R=lambda:[int(i)for i in input().split()]
I=3*10**9
n=int(input())
s,c=R(),R()
r = I
for j in range(n):
    t1 = I
    for i in range(j):
        if s[i] < s[j]:
            t1 = min(t1, c[i])
    t2 = I
    for i in range(j+1, n):
        if s[i] > s[j]:
            t2 = min(t2, c[i])
    r = min(c[j] + t1 + t2, r)
if r < I:
    print(r)
else:
    print("-1")


#R=lambda:list(map(int,input().split()))
"""
R=lambda:[int(i)for i in input().split()]
I=3*10**8
n=int(input())
s,c=R(),R()
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i] for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])
"""
R=lambda:[int(i)for i in input().split()]
I=10**9
n=int(input())
s,c=R(),R()
r = I
for j in range(n):
    t1 = I
    for i in range(j):
        if s[i] < s[j]:
            t1 = min(t1, c[i])
    t2 = I
    for i in range(j + 1, n):
        if s[i] > s[j]:
            t2 = min(t2, c[i])
    r = min(c[j] + t1 + t2, r)
if r < I:
    print(r)
else:
    print("-1")


from sys import stdin 

n = int(stdin.readline())

size = list(map(int,stdin.readline().split()))
price = list(map(int,stdin.readline().split()))

temp = [3*10**8 + 1] * n
ans = [3*10**8 + 1] * n

for i in range(n):
    for j in range(i+1,n) :
        if (size[i] >= size[j]) :
            continue
        temp[j] = min(temp[j],price[i]+price[j])
for i in range(n):
    for j in range(i+1,n):
        if(size[i] >= size[j]):
            continue
        ans[j] = min(ans[j],temp[i]+price[j])
res = 3*10**8 + 1
for i in range(n):
    if (res > ans[i]) :
        res = ans[i]
if (res == 3*10**8 + 1):
    print("-1")
else :
    print(res)





R=lambda:list(map(int,input().split()))
I=2**29
n=int(input())
s,c=R(),R()
r=min(c[j]+min([c[i]for i in range(j)if
s[i]<s[j]],default=I)+min([c[i] for i in range(j+1,n)if
s[i]>s[j]],default=I)for j in range(n))
print((r,-1)[r>I])

R=lambda:map(int,input().split())
I=10**10
n=int(input())
s,c=list(R()),list(R())
r=min(c[j]+min([I]+[c[i]for i in range(j)if
s[i]<s[j]])+min([I]+[c[i]for i in range(j+1,n)if
s[i]>s[j]])for j in range(n))
print((r,-1)[r>I])

n=int(input())
s=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]

cost=min(min([3e10]+[c[j] for j in range(i) if s[j]<s[i]])+c[i]+min([3e10]+[c[k] for k in range(i+1, n) if s[k]>s[i]]) for i in range(n))

if cost>=3e10:   
    cost=-1
print(cost)

def main():
    n = int(input())
    s = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    Max = 2 * sum(c)

    f = [x for x in c]
    # f[i] means when the last element in the 3-elements sequence is the i-th element in the original sequence
    # the minimum cost of the 3-element sequence
    for _ in range(2):
        for i in range(n - 1, -1, -1):
            min_fj = Max
            for j in range(i):
                if s[j] < s[i]:
                    min_fj = min(f[j], min_fj)
            if min_fj == Max:
                f[i] = Max
            else:
                f[i] = min_fj + c[i]

    min_cost = min(f)
    if min_cost == Max:
        print(-1)
    else:
        print(min_cost)


def __starting_point():
    main()

__starting_point()


import sys
import math
import os.path


def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def ni():
    return list(map(int, input().split(" ")))


def nio(offset):
    return [int(x) + offset for x in input().split(" ")]


def nia():
    return list(map(int, input().split()))


CMAX = 1000000000

n, = ni()
s = nia()
c = nia()

# log(f"s = {s}")
# log(f"c = {c}")

# log(f"small = {small}")
l1 = [CMAX for _ in range(n)]
l2 = [CMAX for _ in range(n)]

for j in range(1, n):
    for i in range(j):
        if (s[i] < s[j]):
            # log(f"s[{i}] = {s[i]} s[{j}]={s[j]}")
            l1[j] = min(l1[j], c[i])
            l2[i] = min(l2[i], c[j])

# log(f"l1 = {l1}")
# log(f"l2 = {l2}")

res = CMAX

for i in range(n):
    res = min(res, l1[i] + l2[i] + c[i])

if (res < CMAX):
    print(res)
else:
    print(-1)



import sys
import math
import os.path


def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def ni():
    return list(map(int, input().split(" ")))


def nio(offset):
    return [int(x) + offset for x in input().split(" ")]


def nia():
    return list(map(int, input().split()))


CMAX = 1000000000

n, = ni()
s = nia()
c = nia()

# log(f"s = {s}")
# log(f"c = {c}")

# log(f"small = {small}")
l1 = [CMAX]*n
l2 = [CMAX]*n

for j in range(1, n):
    for i in range(j):
        if (s[i] < s[j]):
            # log(f"s[{i}] = {s[i]} s[{j}]={s[j]}")
            l1[j] = min(l1[j], c[i])
            l2[i] = min(l2[i], c[j])

# log(f"l1 = {l1}")
# log(f"l2 = {l2}")

res = CMAX

for i in range(n):
    res = min(res, l1[i] + l2[i] + c[i])

if (res < CMAX):
    print(res)
else:
    print(-1)



import sys
import math
import os.path


def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def ni():
    return list(map(int, input().split(" ")))


def nio(offset):
    return [int(x) + offset for x in input().split(" ")]


def nia():
    return list(map(int, input().split()))


CMAX = 1000000000

n, = ni()
s = nia()
c = nia()

# log(f"s = {s}")
# log(f"c = {c}")

# log(f"small = {small}")
l1 = {}
l2 = {}

for j in range(1, n):
    for i in range(j):
        if (s[i] < s[j]):
            # log(f"s[{i}] = {s[i]} s[{j}]={s[j]}")
            l1[j] = min(l1.get(j,CMAX), c[i])
            l2[i] = min(l2.get(i,CMAX), c[j])

# log(f"l1 = {l1}")
# log(f"l2 = {l2}")

res = CMAX

for i in range(n):
    res = min(res, l1.get(i, CMAX) + l2.get(i,CMAX) + c[i])

if (res < CMAX):
    print(res)
else:
    print(-1)


from heapq import heappush
import bisect
n=int(input())
s=list(map(int,input().split()))
c=list(map(int,input().split()))
a={}
b=[]
ak=[]
aki=[]
for i in range(n-1,-1,-1):
    ind0=bisect.bisect(ak,s[i])
    ak.insert(ind0,s[i])
    aki.insert(ind0,i)
    a[i]=[]
    ind=-1
    for j in aki[ind0:]:
        if s[j]>s[i]:
            if len(a[j])==1:
                heappush(b,c[i]+c[j]+c[a[j][0]])
            if ind==-1 or m>=c[j]:
                m,ind=c[j],j
    if ind!=-1:
        a[i]=[ind]
if b:
    print(b[0])
else:
    print(-1)

from math import inf

n = int(input())

s = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

dp = [[0, inf, inf, inf][:] for i in range(n)]
dp[0][1] = c[0]

for j in range(1, 4):
    for i in range(1, n):
        for k in reversed(list(range(i))):
            if j == 1 or s[k] < s[i]:
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + c[i])

r = min(x[3] for x in dp)
if r == inf:
    print(-1)
else:
    print(r)