Se citesc doua numere naturale n si m, o matrice cu n linii si m coloane cu valori intre 0 si 9, si o suma S. Determinati, folosind Programarea Dinamica, numarul de drumuri de la celula (1,1) la celula (n,m) (deplasare doar la dreapta sau in jos) a caror suma a valorilor vizitate este exact S.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu m valori (0-9). Pe ultima linie se citeste S.
- Date de iesire
- Se afiseaza un singur numar: numarul de drumuri cu suma S.
- Restrictii
- 1 <= n, m <= 12, 0 <= valoare <= 9, 0 <= S <= 250
Exemple
Exemplul 1
Intrare
2 2 1 2 3 4 7
Iesire
1
Exemplul 2
Intrare
3 3 1 1 1 1 1 1 1 1 1 5
Iesire
6