z-cellphones

In the Z-land there are m x n houses arranged on a regular m by n grid. The mayor of Z-land, mister Little Z, decided to install cellphone lines in each of the houses (since the land-lines are not cool any more).

In the Z-land there are two different cellphone companies: Z-Cell and Z-Mobile. Little Z can use his (government) funds to install any of the two cellphone companies' phones in any of the houses. However, the two companies have totally different pricing strategies. One company bases their prices based on the size of the house, or the number of people living there, or who know what - it's their secret. All that little Z knows is the prices of installing phones in each of the houses for both companies.

However, there is catch! If two adjacent houses (horizontally, vertically, but NOT diagonally - each house have at most 4 adjacent houses) have phones from a different company, then Little Z has to install a signal blocker between the two houses, so that the signals of the two companies do not interrupt each-other. The price of the blocker is X z-dollars.

You have a list of prices for all the houses (and both companies). And you have to help little Z decide which house will use which company so that the overall cost is minimized.