Troll-hunter P89823

El nuevo juego de moda es Troll-Hunter! En él, tienes que escapar de una mazmorra llena de trols. La mazmorra tiene $n$ niveles, y el nivel $i$ tiene $i$ salas. Denotemos con $S[i][j]$ la $j$-ésima sala del nivel $i$. De cada $S[i][j]$ salen exactamente dos pasadizos unidireccionales: uno hacia $S[i+1][j]$ y uno hacia $S[i+1][j+1]$. Además, cada sala $S[i][j]$ tiene $T[i][j]$ trols. Al comenzar el juego te encuentras en $S[1][1]$. Puedes escapar por cualquier sala del nivel $n$.

Después de jugar un poco, has descubierto que siempre puedes superar la primera sala. Después, puedes superar una nueva sala si y sólo si su número de trols no supera el número de trols de la sala acabada de visitar (los mataras con C-ESC o no, sigue leyendo). Pero un amigo te ha explicado un truco: Si aprietas Control+Escape (C-ESC para abreviar), los trols de la sala actual mueren y puedes seguir jugando. Como usar este truco a menudo haría el juego demasiado fácil, tu objectivo es passar el juego con el mínimo número de C-ESCs.

Entrada

La entrada consiste en diversos casos, sólo con naturales, cada uno con $n$ seguida de $n$ linias. La $i$-ésima linea contiene $T[i][1] \dots T[i][i]$. Suponed $2 \le n \le 1000$ y $1 \le T[i][j] \le 10^9$.

Salida

Para cada caso, escrivid el mínimo número de C-ESCs necesarios para pasar la mazmorra.