Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

Konvejeriai

NASA pagaliau sugebėjo nukeliauti į Pandoros planetą. Tiriant planetą buvo rastas didelis paviršiaus plotas pilnas brangių ir žemėje labai retų mineralų - eterio ir triličio. Šį plotą galima atvaizduoti kaip N eilučių ir M stulpelių matricą, kurios kiekvienas langelis turi e eterio ir t triličio. NASA mokslininkai nori surinkti kuo daugiau šių mineralų.

Išsiųsti astronautai rasto ploto šiaurinėje dalyje pastatė eterio perdirbimo fabriką, o vakaruose triličio perdirbimo fabriką. Mineralų pervežimui iš langelių į fabrikus nutarta kiekvienam langelyje pastatyti konvejerį. Konvejeriai yra dviejų tipų: pirmo tipo konvejeris perkelia mineralus iš rytų į vakarus, antro tipo konvejeris perkelia mineralus iš pietų į šiaurę. Vienam langelyje gali būti tik vieno tipo konvejeris.

Kadangi mineralai yra nestabilūs, jie turi būti perkelti į fabriką tiesia linija, kitaip mineralai prarandami. Taip pat, visas eteris nusiųstas į triličio fabriką bus prarastas. Tas pats ir su triličiu nusiųstu į eterio fabriką.

Konvejeriai

Jūsų programa turi sukurti tokią konvejerių sistemą, kad į fabrikus nusiųstų mineralų kiekių suma būtų maksimali.

Pradiniai duomenys

Duomenys sudaryti iš kelių testų.

Pirmoje testo eilutėje duoti du skaičiai N,M(1\\leqN,M\\leq500) - mineralų matricos eilučių ir stulpelių skaičius.

Sekančiose N eilučių duota po M skaičių a_{i,j}(0\\leqe_{i,j}\\leq1000) - triličio kiekis langelyje i,j.

Kitose N eilučių duota po M skaičių a_{i,j}(0\\leqt_{i,j}\\leq1000) - eterio kiekis langelyje i,j.

N=M=0 reiškia testų pabaigą.

Rezultatai

Kiekvienam testui išveskite po vieną skaičių - maksimalią surinktų mineralų sumą.

Pavyzdys

Duomenys Rezultatai 
4 4
0 0 10 9
1 3 10 0
4 2 1 3 
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0
 
98

Pirmo pavyzdžio galimas konvejerių išdėstymas:

Pavyzdys