Plinovod

Mirko je vlasnik velike pekare na rubu grada. Kako je došla kriza, Mirku je račun za plin koji grije njegove pećnice postao prevelik, pa je odlučio preći na onu stranu zakona i krasti plin iz velikog plinovoda koji prolazi blizu njegove pekare. Zemljište u okolici pekare možemo prikazati kvadratnom mrežom dimenzija R×S i to tako da veliki plinovod prolazi svim kvadratima u prvom stupcu, a Mirkova pekara se prostire svim kvadratima u zadnjem stupcu. Mirko će svoje cijevi spojiti na veliki plinovod i provesti ih prema svojoj pekari. Neki kvadrati zemljišta su vrlo nepristupačni i tim kvadratima ne mogu prolaziti Mirkove cijevi. Svaki put od plinovoda prema pekari počinje na nekom kvadratu u prvom stupcu, završava na nekom kvadratu u zadnjem stupcu, a sa svakog kvadrata na putu cijev može voditi na kvadrat koji se nalazi njemu gore-desno, desno ili dolje-desno. Kako bi povukao što više plina iz velikog plinovoda, Mirko želi provesti što je moguće više puteva do svoje pekare. Putevi se međusobno ne smiju križati niti dodirivati, odnosno jednim kvadratom može prolaziti najviše jedan put plina. Napišite program koji će odrediti koliko je najviše puteva moguće paralelno provesti preko zadanog zemljišta.