Chess Board

allis Brook and Helen Heather like playing chess. Today they are not going to play chess buthave a competition on drawing a chess board. The chess board they used are a bit different from the ordinary one. The chess board consist of n rows and each row has m white square cells of the same size. Adjacent cells are seperated with a black border. There are also black borders on the edge of the chess board. Each border has the same width. The following figure shows how the chess board looks like. To make it like a chess board more, it is also constrained that the length of the cell should be no shorter than the width of the border, i.e. a ≥ b.

Now they are given a black-and-white image. They are going to make it a chess board as mentioned above. They both want to finish it faster than the other one.

In order to win the competition, Vallis managed to know how Helen would draw the chess board. Each time, Helen can draw a rectangle with one color and all the pixels in the rectangle will be painted with that color. He needs time T to draw one rectangle. In addition, he will only paint each pixel with the target color. That is to say, there will be no pixel to be painted multiple times with different colors. Because Vallis is busy drawing the chess board pixel by pixel, he ask you to help him calculate the minimum time for Helen to finish the job.

There are multiple test cases. The first line of each test case contains five integers H, W, n, m and T (3 ≤ H, W ≤ 2000, 1 ≤ n, m ≤ 200, 0 < T ≤ 1000), indicating the height and the width of the image, the numbers of rows and columns and the time Helen needs to draw a rectangle. Then H lines follows, each of which contains W 0 or 1, indicating the image. 0 means the color of that pixel is black and 1 means white.

Output the minimum time Helen needs to finish the chess board if it is possible to draw one. Otherwise, output -1 instead.

3 5 1 2 1
00000
01110
01110
5 7 1 2 1
0000000
0000000
0000000
0000000
0000000

2
-1

GUAN, Yao

2011 Asia Dalian Regional Contest