Pintant cases P70058

En un carrer hi ha $n$ cases. La façana de cada casa $i$ es pot pintar amb tres colors diferents, amb costs respectius $c_{1i}$, $c_{2i}$ i $c_{3i}$. Calculeu el cost mínim de pintar totes les cases, amb una restricció: les cases adjacents han de tenir colors diferents.

Entrada

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

Sortida

Per a cada cas, escriviu el cost mínim de pintar les $n$ façanes.