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] … T[i][i]. Suposeu 2 ≤ n ≤ 1000 i 1 ≤ T[i][j] ≤ 10⁹.

Sortida

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