City Planning

Time limit2sMemory limit512 MB

Summary

Choose a threshold Z so all cells with elevation at most Z hold skyscrapers, tile every remaining cell with adjacent pairs (parks), and minimize Z*W plus D per park.

Level: Medium7 of 10
Topics: Greedy, Graph, Sorting, Implementation
Solved: No attempts yet

Problem

You are planning a new city. You must decide where to put skyscrapers and parks in the city. The city consists of R x C blocks and is represented as a grid with R rows and C columns. For example, the figure below shows a city with 2 rows and 3 columns. It has six blocks in total. Each block has one integer value indicating its elevation above sea level.

When building skyscrapers and parks in the city, all of the following conditions must hold.

One skyscraper must be built on one block. That is, a skyscraper cannot span two blocks.
Each block must either have one skyscraper or be part of a park.
If a block with a skyscraper has elevation y, then every block with elevation at most y must also have a skyscraper.
A park must be built on two adjacent blocks, and two different parks must not overlap. That is, a block cannot belong to two parks. Also, a park must not extend outside the grid of blocks.

Because of condition 3, when planning the city you must first choose a non-negative integer Z. Then you build skyscrapers on all blocks with elevation at most Z and build parks on the remaining blocks. A park must be built on two adjacent blocks. Two blocks are adjacent when they share a road.

Building one park costs D won. The total cost of building the skyscrapers is Z×W won.

Write a program that finds the minimum cost of building the skyscrapers and parks while satisfying all of the conditions above.

Input

The first line gives four integers R, C, D, W (1 ≤ R, C ≤ 50 and 1 ≤ D, W ≤ 10⁹). Each of the next R lines gives C integers. These numbers are the elevation values y of the blocks. Each y is between 1 and 10⁹ inclusive.

Output

On the first line, print the minimum cost needed to build skyscrapers and parks on all blocks.

Note

Participants using Python are advised to use PyPy.

In the example in the figure above, choosing Z = 10 lets you build skyscrapers on the top-left and bottom-right blocks and two parks on the remaining blocks.

The three examples below show parks built without following this rule.

The left example shows a park that extends outside the city grid. The middle example shows two parks that overlap and are built on one block. They share the top middle block. The right example shows a park that is not built on two adjacent blocks. In all three cases the park is built incorrectly.

Examples5

Example 1
Input
```
2 3 120 10
10 30 20
40 20 10
```
Expected output
```
340
```
Example 2
Input
```
1 2 76 59
62 77
```
Expected output
```
76
```
Example 3
Input
```
1 4 71 87
41 2 95 68
```
Expected output
```
142
```

Example 4

Input

Expected output

Example 5

Input

4 4 71 3
85 86 97 99
30 74 50 88
77 78 34 83
59 26 54 63

Expected output