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.

INPUT:
From the first line of the standard input read three integers m, n, and X, with 1 <= m, n <= 50, and 0 <= X <= 1000000. From each the next m lines read n integers representing the prices of the Z-Cell for the given house. Finally from each of the next m lines read n integers representing the prices for Z-Mobile. All the prices will be in the range [0 1000000].

OUTPUT:
To the standard input write one integer, representing the minimal amount of z-dollars needed in order to equip each house with a phone from one of the two cellphone companies

Input:

Output:

Explanation: we have the following assignment (with C being Z-Cell and M being Z-Mobile)

For this assignment we need two blockers, hence the total price is: 1+1+1+4+4+4 = 15 z-dollars

Input:

Output:

Explanation: we have the following assignment (with C being Z-Cell and M being Z-Mobile)

Now we don't need any blockers, hence the total price is 4 x 4 = 16 z-dollars