Kupiec
Limit pamięci: 32 MB
Bajtazar jest wędrownym kupcem, który przemieszcza się pomiędzy miastami
leżącymi wzdłuż linii kolejowej.
Jego cel jest prosty: kupić tanio, sprzedać z zyskiem
i nie wydać zbyt dużo na podróż.
Wspomniane miasta są ponumerowane od do zgodnie
z kolejnością występowania wzdłuż torów.
Bajtazar chciałby zarobić możliwie najwięcej na pewnym konkretnym towarze, którego
cenę w każdym mieście zna.
Ponadto wie, ile kosztuje przejazd między dowolną parą sąsiadujących miast
(droga w okolicy jest tylko jedna, więc bezpośrednio można poruszać się
jedynie pomiędzy miastami o numerach oraz ).
Jego zysk to cena, po której sprzeda towar, pomniejszona o cenę zakupu
i sumaryczny koszt przejazdu. Niestety Bajtazar nie jest zbyt dobry z ekonomii i
potrzebuje Twojej pomocy.
Napisz program, który obliczy maksymalny możliwy zysk w jednej takiej
parze transakcji, zakładając, że Bajtazar może rozpocząć i zakończyć
podróż w dowolnych miastach.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę miast.
W drugim wierszu znajduje się liczb całkowitych
() pooddzielanych pojedynczymi odstępami.
Są to ceny towaru w kolejnych miastach.
Trzeci wiersz zawiera liczb całkowitych
( dla ) pooddzielanych pojedynczymi odstępami, oznaczających
ceny przejazdu odpowiednio między miastami o numerach oraz .
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę
całkowitą - maksymalny możliwy zysk Bajtazara.
Zauważ, że w skrajnym przypadku Bajtazar może kupić i sprzedać towar w tym samym mieście.
Przykład
Dla danych wejściowych:
4
19 5 2 3
5 1 1
poprawną odpowiedzią jest:
11
Wyjaśnienie do przykładu:
Bajtazar kupuje towar w mieście numer 3 (cena: 2),
następnie przejeżdża do miasta numer 1 (koszt tego przejazdu to ),
gdzie sprzedaje towar w cenie 19.
Łączny zysk Bajtazara to: .
Autor zadania: Michał Włodarczyk.