Troll-hunter P89823

El nou joc de moda és Troll-Hunter! En aquest joc, s’ha d’escapar d’una masmorra plena de trols. La masmorra té $n$ nivells, i el nivell $i$ té $i$ sales. Denotem amb $S[i][j]$ la $j$-èsima sala del nivell $i$. De cada $S[i][j]$ surten exactament dos pasadissos unidireccionals: un cap a $S[i+1][j]$ i un cap a $S[i+1][j+1]$. A més, cada sala $S[i][j]$ té $T[i][j]$ trols. En començar el joc et trobes a $S[1][1]$. Et pots escapar per qualsevol sala del nivell $n$.

Després de jugar una mica, has descobert que sempre pots superar la primera sala. Després, pots superar una nova sala si i només si el seu nombre de trols no supera el nombre de trols de la sala acabada de visitar (els matessis amb C-ESC o no, segueix llegint). Però un amic t’ha explicat un truc: Si prems Control+Escape (C-ESC per abreujar), els trols de la sala actual moren i pots seguir jugant. Com utilitzar aquest truc sovint faria el joc massa fàcil, el teu objectiu és passar el joc usant el mínim de nombre de C-ESCs.

Entrada

L’entrada consisteix en diversos casos, només amb naturals, cadascun amb $n$ seguida de $n$ línies. La $i$-èsima línia conté $T[i][1] \dots T[i][i]$. Suposeu $2 \le n \le 1000$ i $1 \le T[i][j] \le 10^9$.

Sortida

Per a cada cas, escriviu el mínim nombre de C-ESCs que calen per passar la masmorra.