Од кога ги научил малите мечиња да собираат броеви, Мендо решил да се посвети на домаќинските работи и да ги обои прозорците од својата еднокатна куќа. Прозорците ги има во секоја соба и се наоѓаат сите на иста височина, па кога Мендо шета околу куќата и ги гледа од надвор прозорците изгледаат како да се наредени во низа. Мендо има три вида на бои (бела, сива и сина) и сака да ги обои прозорците така што нема да постојат два прозорци кои се со иста боја и се наоѓаат еден после друг.

Напишете програма која од стандарден влез ќе прочита информации за бројот на прозорци и цената на боење на секој од нив со одредена боја, па на стандарден излез ќе ја испечати минималната цена на боење на сите прозорци.

Влез

Во првата линија е запишан еден цел број N (2 <= N <= 20), кој го означува бројот на прозорци. Во секој од следните N редови се запишани по 3 цели броја Ai, Bi, Ci (1 <= Ai, Bi, Ci <= 1000), каде Ai, Bi, и Ci ги означуваат цените на боење на i-тиот прозорец со бела, сива и сина боја, соодветно.

Излез

Излезот се состои од еден цел број – минималната цена на боење на сите прозорци. Имајте предвид дека првиот (1) и последниот (N-тиот) прозорец се соседни.

Ограничувања

Временско ограничување: 2 seconds
Мемориско ограничување: 64 megabytes

Примери

влез
3
5 1 5
1 5 5
5 1 1

излез
3

Објаснување: Мендо може да го обои првиот прозорец со сива боја, вториот прозорец со бела боја и последниот (третиот) прозорец со сина боја за цена 1+1+1=3. На тој начин, нема да постојат два соседни прозорци со иста боја.