Gigel este extrem de pasionat de numismatică şi din această cauză colecţionează monede. Ca să le păstreze el le-a grupat în N şiruri, numerotate de la 1 la N, ce cuprind fiecare câte M teancuri de monede. În cadrul unui şir, teancurile sunt numerotate de la 1 la M în ordine de la stânga la dreapta. Fiecare teanc conţine un număr oarecare de monede.
Lui Gigel i se permite un singur tip de operaţie: mutarea unui număr oarecare de monede dintr-un teanc şi plasarea acestora într-un alt teanc, situat în alt şir.
Gigel doreşte ca toate teancurile cu numărul i (pentru orice 1≤i≤M), din toate cele N şiruri, să conţină acelaşi număr de monede. Pentru aceasta poate efectua oricâte operaţii permise doreşte.
Cerinţă
Scrieţi un program care determină numărul minim de monede care trebuie mutate de Gigel prin operaţii permise astfel încât la final toate teancurile să respecte regula descrisă în enunţ.
Date de intrare
Fişierul de intrare monede2.in conţine pe prima linie două numere naturale N şi M, separate printr-un spaţiu, reprezentând numărul de şiruri, respectiv numărul de teancuri din fiecare şir. Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de monede din fiecare teanc, în ordine de la stânga la dreapta.
Date de ieşire
Fişierul de ieşire monede2.out va conţine o singură linie pe care va fi scris numărul minim de monede determinat.
Restricţii
• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 1000
• 0 ≤ numărul iniţial de monede din fiecare teanc ≤ 10000
• Se garantează că orice test admite soluţie
Exemple
monede2.in
monede2.out
Explicaţii
2 4
1 2 7 5
4 2 9 6
3
Se ia o monedă din primul teanc din al doilea şir şi o plasăm pe teancul al patrulea din primul şir. Se obţine:
1 2 7 6
3 2 9 6
Se iau două monede din al treilea teanc din şirul doi şi se plasează în primul teanc din primul şir. Se obţine:
3 2 7 6
3 2 7 6
Observaţi că după efectuarea a două operaţii permise, în care s-au mutat în total 3 monede, teancurile cu acelaşi număr de ordine conţin acelaşi număr de monede.
Există şi alte succesiuni de operaţii permise, prin care se poate obţine acelaşi număr minim de monede mutate (3).