Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3308
Move the Knights

Time Limit: 5 Seconds      Memory Limit: 32768 KB

In order to celebrate the 8th anniversary of ZOJ, ZJU ACM team members are playing a game named "Move the Knights".

Given a chessboard with size R x C. The row number and column number are all indexed from 1, each grid has a power value P(row,col) related with it. There are 3 kinds of knights in this game, called "Gold Knight", "Silver Knight" and "Bronze Knight", respectively. They can only be moved to one of the eight positions as the following gragh shows, and cannot be moved out of the board of course. When transferred from one position to another, the Knight will lose a certain quantity of energy according to the power value of the two girds and the type of the knight, for example, from Grid(row1,col1) to Gird(row2,col2), Gold Knight will lose P(row1,col1) x P(row2,col2) energy, Silver Knight will lose P(row1,col1) + P(row2,col2) energy, and Bronze Knight will loss max( P(row1,col1), P(row2,col2) ) energy.

Initially, N knights are placed in black grids. The goal of this game is to move EXACTLY K (K <= N) Knights with minimal energy.

Note that each Knight can be moved ONLY ONCE, and every grid can be occupied by one knight at most. The Grid(row,cow) is black when and only when (row + col) mod 2 = 0.

Input

There are multiple cases(no more than 50).

Each test case starts with a line, which contains 4 positive integers, R C N K (1 <= R, C <= 15, 1 <= N <= RxC/2, 1 <= K <= N). Then R lines follow, each contains C positive integers, the cth integer of the rth line inditating the power value (1 <= P(r,c) <= 10) of that grid. Then N lines follow, each contains three positive integers: type ri ci (1 <= type <= 3, 1 <= ri <= R, 1 <= ci <= C). Type 1 indicates Gold Knight, type 2 indicates Silver Knight and type 3 indicates Bronze Knight, ri and ci are the position of that knight, it is guaranteed that Grid(ri,ci) are all black grids.

Output

For each test case, output a single line containing the minimal energy lost when the K knights moved. If there is no solution, output -1 instead.

Sample Input

```3 4 2 2
1 1 1 1
2 2 2 2
3 2 3 4
2 1 1
1 1 3
3 3 1 1
1 1 1
2 2 2
3 3 3
3 2 2
```

Sample Output

```5
-1
```

Hint

Case 1: Move the Silver Kight from Grid(1,1) to Grid(2,3) and move the Gold Kight from Grid(1,3) to Grid(3,2) achieve the goal.

Case 2: You hava no way to move the Bronze Knight, just output -1.

Author: FU, Changlin
Source: ZOJ 8th Anniversary Contest
Submit    Status