12 Urodziny Polskiego SPOJa

Mariusz Pudzianowski wybrał się na spacer po parku. Wzdłuż jednej z alejek, ustawionych jest n beczek. Na każdej z nich znajduje się kamienna kula. Kule ponumerowane są kolejnymi liczbami naturalnymi od 1 do n.

Nasz bohater postanowił przeprowadzić trening siłowy jak za dawnych lat. W tym celu chce wybrać 3 kule o numerach i, j oraz k spełniające następujące warunki:

1. i < j < k
2. w(i) < w(j) < w(k)
3. h(i) > h(j) > h(k)

Gdzie w(x) oznacza wagę kuli o numerze x, zaś h(x) oznacza wysokość beczki, na której znajduje się kula o numerze x. Jeżeli 3 kule spełniające powyższe warunki można wybrać na więcej niż jeden sposób, Mariusz wybierze ten, w którym łączna waga kul jest największa.

Odpowiedz na pytanie, ile łącznie będą ważyły kule wybrane przez naszego bohatera?

Wejście

W pierwszej linii wejścia znajduje się liczba kul n ∈ [1, 8000].

W drugiej linii wejścia znajduje się n liczb naturalnych z przedziału [1, 10⁸]. Liczba i-ta w kolejności oznacza wagę kuli o numerze i.

W trzeciej linii wejścia znajduje się n liczb naturalnych z przedziału [1, 10⁸]. Liczba i-ta w kolejności oznacza wysokość beczki, na której stoi kula o numerze i.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile łącznie będą ważyły kule wybrane przez naszego bohatera?

W przypadku, gdy nie można wybrać 3 kul spełniających powyższe warunki, należy wypisać 0.

Przykład 1

Wejście:

8
225 200 150 300 275 175 250 260
140 150 170 100 110 160 130 120

Wyjście:

735

Wyjaśnienie do przykładu:

Istnieje 6 sposobów wybrania 3 kul, tak aby spełniały powyższe warunki:

• 1, 7, 8 - łączna waga 735
• 2, 7, 8 - łączna waga 710
• 3, 6, 7 - łączna waga 575
• 3, 6, 8 - łączna waga 585
• 3, 7, 8 - łączna waga 660
• 6, 7, 8 - łączna waga 685

Spośród nich Mariusz wybierze sposób 1, gdyż to w nim łączna waga kul jest największa.

Przykład 2

Wejście:

5
100 150 100 150 150
120 110 100 95 94

Wyjście:

0