408059: GYM102968 I Orchards

The year is 2121. The first humans have reached the planet AGMinia and established a small settlement. They now want to build a number of orchards on a carefully chosen piece of land. However, due to the special climate on the newly discovered planet, they must follow a number of rules as described below.

The land is represented by a two dimensional array of $$$N$$$ rows and $$$M$$$ columns. Each cell of the land has its own height.

The $$$K$$$ non-overlapping orchards they want to build are represented by rectangles within the main piece of land. Two orchards $$$g_1$$$ and $$$g_2$$$ are considered adjacent if there are any two cells $$$c_1$$$ and $$$c_2$$$ such that $$$c_1$$$ is within $$$g_1$$$ and $$$c_2$$$ is within $$$g_2$$$ and $$$c_1$$$ and $$$c_2$$$ are adjacent vertically, horizontally or diagonally.

All the cells within an orchard must be leveled, i.e. have the same height. In order to achieve this, the humans can use advanced technology to increment or decrease the height of a cell by 1. Such an operation can be performed an unlimited number of times on a given cell provided that the height doesn't go below 1. The cost of performing the operation once is 1.

Moreover, due to the special conditions on the planet, any two adjacent orchards must have different heights. And because it is easier to control the weather at the same height, there must be at most two distinct heights among all orchards after they are leveled.

Help the humans improve the new settlement and compute the minimum cost they will need in order to achieve this goal.

The first line of the input contains $$$3$$$ integers: $$$N, M, K$$$ (the number of rows and columns of the land, respectively, and the number of orchards).

Each of the following $$$K$$$ lines contains $$$4$$$ integers $$$x_1, y_1, x_2, y_2$$$. $$$(x_1, y_1)$$$ represents the upper-left corner of the $$$i^{th}$$$ orchard and $$$(x_2, y_2)$$$ represents the bottom-right corner of the same orchard.

The next $$$N$$$ lines contain $$$M$$$ integers each, describing the heights of the land. $$$1 \leq N, M \leq 1000$$$ and $$$1 \leq K \leq 500$$$.

$$$1 \leq x_{i1} \leq x_{i2} \leq N, 1 \leq y_{i1} \leq y_{i2} \leq M$$$, for all $$$1 \leq i \leq K$$$.

$$$0 \leq$$$ height of any cell $$$\leq 100$$$.

$$$1 \leq$$$ height of any cell within an orchard $$$\leq 100$$$.

It is guaranteed that no two orchards will overlap.

The output should contain one integer, representing the minimum possible cost needed to complete the task, or -1 if it is not possible.

3 5 3
1 1 2 3
1 5 2 5
3 1 3 3
1 1 1 0 1
1 1 1 0 2
1 2 2 0 0

2

1 5 3
1 1 1 1
1 3 1 3
1 5 1 5
7 2 7 4 7

0

1 5 3
1 1 1 1
1 3 1 3
1 5 1 5
7 2 8 4 9

1

2 2 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
1 1
1 1

-1

In the first example, there are two adjacent orchards (the first and the last one). The first orchard is already leveled. We can level the third one by increasing the height of the first cell of the third row with one. For the second orchard, we can either increase the shorter cell or decrease the other one. Two operations is the best we can do here, thus the answer is 2.

For the second example, all the orchards are already leveled as they each contain only one cell and none of them is adjacent to another one. All the criteria is satisfied without having to perform any operation, hence the cost is 0.

In the third example, the orchards consist of only one cell each, this time having the heights 7, 8 and 9 respectively. We must have at most two distinct heights, so we have to apply one operation here, for example decrease the third one to 8.

In the last example it is impossible to complete the task without breaking any of the rules.