세 개의 디스플레이

2018년 중반, Krasnokamensk(Zabaikalsky 지역의 도시) 외곽에 사는 Maria Stepanovna는 중요한 문제를 알리기 위해 디스플레이 세 개를 빌리려고 한다.

도로를 따라 n개의 디스플레이가 설치되어 있으며, 그중 i-th 디스플레이에는 글꼴 크기 $s_i$인 텍스트만 표시할 수 있다. Maria Stepanovna는 특정 방향으로 도로를 따라 이동할 때 글꼴 크기가 증가하도록 인덱스 i < j < k인 디스플레이 세 개를 빌리려고 한다. 즉, 조건 $s_i$ < $s_j$ < $s_k$을 만족해야 한다.

i-th 디스플레이의 대여 비용은 $c_i$이다. Maria Stepanovna가 지불해야 하는 최소 비용을 구한다.

첫 번째 줄에 디스플레이의 수를 나타내는 정수 n (3 ≤ n ≤ 3 000)이 주어진다.

두 번째 줄에 디스플레이가 도로를 따라 설치된 순서대로 각 디스플레이의 글꼴 크기를 나타내는 n개의 정수 $s_1$, $s_2$, …, $s_n$ (1 ≤ $s_i$ ≤ $10^9$)가 주어진다.

세 번째 줄에 각 디스플레이의 대여 비용을 나타내는 n개의 정수 $c_1$, $c_2$, …, $c_n$ (1 ≤ $c_i$ ≤ $10^8$)가 주어진다.

조건을 만족하는 디스플레이 세 개가 없다면 -1을 출력한다. 그렇지 않으면 i < j < k이고 $s_i$ < $s_j$ < $s_k$인 인덱스를 갖는 디스플레이 세 개의 최소 총 대여 비용을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 예를 들어 디스플레이 1, 4, 5를 선택할 수 있다. $s_1$ < $s_4$ < $s_5$ (2 < 4 < 10)이기 때문이며, 대여 비용은 40 + 10 + 40 = 90이다.

두 번째 예제에서는 유효한 인덱스 세 개를 선택할 수 없으므로 답은 -1이다.