Esperit nadalenc P19910

En un passeig hi ha lloc per a $n$ decoracions nadalenques, cadascuna de les quals pot ser un arbre, un pessebre o una llum. Una empresa pot instal·lar-ho tot. Per a tota $1 \le i \le n$, el preu de posar en el lloc $i$-èsim un arbre, un pessebre o una llum seria $p_{1i}$, $p_{2i}$ i $p_{3i}$, respectivament. Podeu calcular el preu mínim d’omplir els $n$ llocs?

Tingueu en compte dues coses:

• No hi pot haver dues (o més) decoracions consecutives del mateix tipus. Per exemple, al costat d’un pessebre no n’hi pot haver cap altre.

• L’amo de l’empresa instal·ladora té bon cor, i ha promès que cobrarà només la meitat del preu total. Però, com que l’home no sap dividir amb decimals, només farà aquest descompte si el preu total és parell.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, seguida de $p_{11}$, $p_{12}$, …, $p_{1n}$, seguits de $p_{21}$, $p_{22}$, …, $p_{2n}$, seguits de $p_{31}$, $p_{32}$, …, $p_{3n}$. Suposeu $1 \le n \le 10^5$, i que tots els preus es troben entre 0 i $10^9$.

Sortida

Per a cada cas, escriviu el preu mínim de decorar el passeig.