Un turist doreşte să viziteze cele N oraşe de pe malul Dunării.
Acestea sunt numerotate cu numere naturale cuprinse între 1 şi N în sensul de curgere.
Oraşul 1 (de plecare) se află la izvoare, iar oraşul N la vărsarea în Marea Neagră.
Turistul se poate deplasa între oricare două oraşe vecine, la alegere, cu vaporul, microbuzul sau elicopterul.
Se cunoaşte costul deplasării între oricare două oraşe vecine cu fiecare dintre cele trei mijloace de transport.
De asemenea, dacă într-un anumit oraş se schimbă mijlocul de transport se cunoaşte costul deplasării în oraşul respectiv
pentru folosirea altui mijloc de transport.
Cerinţă
Determinaţi costul minim cu care turistul poate vizita toate cele N oraşe de pe valea Dunării ştiind că el pleacă din portul corespunzător oraşului de la izvoare.
Date de intrare
Fişierul de intrare fluviu.in are următoarea structură:
- pe prima linie N, numărul de oraşe de pe valea Dunării;
- pe linia a doua, N numere naturale reprezentând costul deplasării între port şi autogară, respectiv, pentru fiecare oraş (al i – lea număr reprezintă costul deplasării între portul şi autogara din oraşul i);
- pe linia a treia, N numere naturale reprezentând, respectiv, costul deplasării între port şi helioport pentru fiecare oraş de la 1 la N.
- pe linia a patra, N numere naturale reprezentând, respectiv, costul deplasării între autogară şi helioport pentru fiecare oraş de la 1 la N.
- Pe linia a cincea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu vaporul între oraşele i şi i+1;
- Pe linia a şasea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu microbuzul între oraşele i şi i+1;
- Pe linia a şaptea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu elicopterul între oraşele i şi i+1.
Date de ieşire
Fişierul fluviu.out va conţine o singură linie pe care va fi scris un număr reprezentând costul minim cu care turistul îşi poate îndeplini dorinţa.
Restricţii
2 <= N <= 50000
Costurile de deplasare între orice 2 oraşe consecutive sau între punctele de plecare din acelaşi oraş sunt numere naturale mai mici decât 2 miliarde.
Din oraşul i se poate merge direct doar în oraşul i+1 cu oricare dintre mijloacele de transport.
Distanţele dintre punctele de plecare ale fiecărui oraş se pot parcurge în ambele sensuri cu acelaşi cost.
Rezultatul este un număr natural ce poate fi memorat pe 32 biţi cu semn.