S1 - Štafeta

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Traja študenti rýchlostného programovania sa chcú pripraviť na ďalšiu tímovú súťaž v programovaní. Na súťaži riešia všetci traja spolu za jedným počítačom niekoľko úloh za stanovený čas - vždy je za počítačom len jeden z nich. Vyučujúci im to chce spestriť, tak im dá úlohy v rámci prípravy riešiť štafetovo. Teda zadané úlohy rieši najprv jeden z nich, potom druhý a nakoniec tretí z nich. Študenti si musia zvoliť poradie v akom budú riešiť (t.j. kto začne a kto pôjde druhý), ale úlohy musia riešiť v danom poradí (od prvej po poslednú, ďalšia sa im totiž zobrazí až keď vyriešia aktuálnu). Každý z nich musí vyriešiť aspoň jednu úlohu.
Učiteľ už pozná schopnosti študentov, takže vie zhodnotiť obtiažnosť úlohy pre každého z nich - od 1 po 5. Pomôžte mu určiť akú najmenšiu celkovú obtiažnosť môžu študenti dosiahnuť (teda súčet obtiažností nimi riešených úloh), aby teda vedel ohodniť či sa rozhodli optimálne.

Úloha

Pre zadané obtiažnosti úloch pre trojčlenný tím, nájdite minimálnu celkovú obtiažnosť pre riešenie úloh štafetovým spôsobom.

Vstup

V prvom riadku súboru sa nachádza číslo N udávajúce počet úloh.

Nasledujú 3 riadky, pričom každý z nich obsahuje N čísel (v rozsahu 1 až 5) určujúcich obtiažnosť danej úlohy.

Výstup

Výstupom programu je jeden riadok obsahujúci jedno kladné celé číslo - minimálny súčet.

S1: 3 ≤ N ≤ 2 000
S2: 3 ≤ N ≤ 100 000

Príklad

Vstup:

7
2 4 1 5 1 1 2
3 3 2 5 3 2 2
1 1 5 4 3 3 3

Výstup:

Optimum je možné dosiahnuť, ak budú riešiť v poradí: tretí (2 úlohy), prvý (4), druhý (1).

16 Domáce 1