Se da o matrice A cu m linii si n coloane, cu elemente numere intregi. Se pot alege, independent, semnele fiecarei linii si fiecarei coloane (fiecare linie si fiecare coloana poate fi inmultita cu -1 sau lasata neschimbata, in orice combinatie, inclusiv toate sau niciuna).
Dupa aplicarea acestor operatii, elementul de pe linia i si coloana j devine r_i * c_j * A[i][j], unde r_i si c_j sunt semnele alese (+1 sau -1) pentru linia i, respectiv coloana j.
Care este suma maxima a elementelor matricei ce poate fi obtinuta in acest fel?
- Date de intrare
- Pe prima linie se citesc doua numere intregi m si n. Pe urmatoarele m linii se citesc cate n numere intregi, elementele matricei.
- Date de iesire
- Se afiseaza un singur numar intreg: suma maxima obtinabila.
- Restrictii
- 1 <= m <= 8 1 <= n <= 10 |A[i][j]| <= 1000
Exemple
Exemplul 1
Intrare
4 5 4 -1 6 4 -5 -2 -33 -12 10 -11 1 0 3 -1 4 -99 -98 -40 34 33
Iesire
361
Exemplul 2
Intrare
1 1 -7
Iesire
7