C2 - Capture The Flag 2

Časový limit: 3s, 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 zamestnanci univerzitného CSIRT tímu sa chcú pripraviť na ďalšiu tímovú súťaž v kyberbezpečnosti - Capture The Flag, kde sa rieši niekoľko úloh. Obdobnú súťaž pripravujú aj pre stredoškolských študentov v rámci projektu Nauč sa základy informačnej bezpečnosti a vzdelávaj svoje okolie
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. Keďže nesúťažia prvýkrát, tak si to chcú spestriť (a sťažiť), rozhodli sa v rámci prípravy riešiť úlohy štafetovo. Teda prvé zadané úlohy rieši najprv jeden z nich, potom druhý ďalšie a nakoniec tretí z nich zvyšné. Poradie v akom budú riešiť (t.j. kto začne a kto pôjde druhý) si môžu zvoliť sami, 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.
Ich šéf už pozná ich schopnosti, 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 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.

C1

3 ≤ N ≤ 2 000

C2

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).

20 Domáce 2