Seiful bancii romane este format din
N siruri a cate M
sertare de dimensiuni egale dispuse unul langa altul. Dimineata cand se deschide
banca toate sertarele sunt inchise. In timpul zilei banca va primii bani (monede),
iar angajatii bancii vor pune monedele in sertare aleatoare. La sfarsitul zilei
un robot trebuie sa rearanjeze monedele astfel incat in toate sertarele deschise
sa fie aceelasi numar de monede. El nu va lua in considerare sertarele inchise.
Robotul se misca doar orizontal sau vertical. Efortul facut de robot pentru
a muta P
monede este egal cu P*nr, unde font face="Courier New, Courier, mono">nr este numarul de sertare peste care trece robotul.
Cerinta
Scrieti un program care sa gaseasca
efortul minim efectuat de robot pentru a rearanja monedele. Se garanteaza existenta
unei solutii.
Date
de intrare
Pe prima linie a fisierului de intrare monede1.in sunt scrise numerele naturale
N M separate printr-un singur spatiu.
Pe urmatoarele N linii sunt scrise cate M numere separate prin spatii reprezentand numarul de monede din sertare. Daca
numarul de monede este 0 inseamna
ca sertarul este inchis si nu va fi luat in considerare de robot.
Date de iesire
Prima linie a fisierului monede1.out va contine efortul minim cerut.