Problem
In una tabella rettangolare NxM (in ogni cella in cui è scritto un certo numero), all'inizio il giocatore si trova nella cella in alto a sinistra.
In una sola mossa, può spostarsi alla cella successiva a destra o in basso (è vietato spostarsi a sinistra e in alto).
Quando attraversa una cella, il giocatore paga tanto c.u.
È necessario trovare l'importo minimo di c.u., pagando il quale il giocatore può arrivare nell'angolo in basso a destra.
Inserimento:
- la prima riga contiene due numeri N e M - dimensioni della tabella (\(1<=N<=20 \), \(1<=M<=20\));
- poi ci sono N righe di numeri M in ciascuna - dimensioni delle multe in c.u. per passare attraverso le celle corrispondenti (ogni numero da 0 a 100).
Output: stampa l'importo minimo che puoi spendere per ottenere nell'angolo in basso a destra.
Esempi
| # |
Input |
Uscita |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |