Fermierul Ionica are un teren de forma dreptunghiulara, impartit in $MxN$ zone unitare ({$M$} este numarul de linii, iar $N$ este numarul de coloane). In urma poluarii generate de uzina din apropiere, o parte dintre zone au fost afectate, astfel incat in zonele acelea nu mai poate fi cultivata momentan nici o planta. Pentru a putea cultiva din nou plante in acele zone, fermierul Ionica va trebui sa curete zonele respective. Pentru aceasta, el poate inchiria niste utilaje pentru indepartarea poluarii. Fiecare utilaj va fi amplasat initial intr-o zona afectata. Din zona initiala, un utilaj poate fi deplasat in orice zona afectata adiacenta (pe orizontala sau verticala) si asa mai departe, pana cand utilajul ajunge intr-o zona finala, de unde firma de la care a inchiriat fermierul utilajul va veni sa il ridice. Fiecare zona prin care trece un utilaj este curatata complet (inclusiv zona initiala si cea finala).

!problema/clear?hc.gif!
 
 

Firma care inchiriaza utilajele ofera $2$ tipuri de contracte de inchiriere. Primul tip de contract permite amplasarea unui utilaj in orice zona afectata, deplasarea acestuia prin oricate zone afectate (poate sa nu fie deplasat deloc din zona initiala) si ridicarea acestuia din orice zona finala. Al doilea tip de contract permite amplasarea unui utilaj in orice zona afectata, insa pune conditia ca utilajul sa fie deplasat prin cel putin 4 zone afectate distincte (inclusiv zona initiala), iar zona finala sa fie aceeasi cu zona initiala. In cazul ambelor tipuri de contracte se permite inchirierea oricarui numar de utilaje.
Fermierul Ionica are si el propriile lui conditii. Un utilaj inchiriat nu trebuie sa treaca de mai multe ori prin aceeasi zona (cu exceptia zonei initiale, in cazul tipului $2$ de contract), iar prin zonele neafectate nu trebuie sa treaca nici un utilaj. De asemenea, el doreste ca prin fiecare zona afectata sa treaca exact un singur utilaj.