Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

UPS12_B - Kule

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, 108]. 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, 108]. 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

Dodane przez:Maciej Boniecki
Data dodania:2019-03-20
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:12 Urodziny Polskiego Spoja
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.