As is well known, Little C is a master of the game "Happy Xiaoxiaole," while Little Z is not very good at games that require even a little bit of thinking. During the May Day holiday, Little C, feeling bored, decided to teach Little Z.
After five days and five nights of non-stop teaching, Little Z finally grasped some of the tricks (Little Z's inner monologue: if only I could show this much enthusiasm for learning probability theory...). However, both of them ignored the fact that this game is addictive. More importantly, Little Z is from Shandong, so he decided to incorporate some local flavor...
Little Z: "...As everyone knows, Dezhou is in Shandong, so let's call it 'Dezhou Xiaoxiaole'!"
Little C quickly stopped him, saying, "Forget it, have you forgotten the big mess of a board last time? Besides, this Dezhou is not that Dezhou! If you want to do this, do it yourself, don't drag me into it."
Before he could finish, Little Z threw the rules at Little C.
Little C: "This is actually pretty good."
Description
Given an $n \times m$ board, let the top-left coordinate be $(1,1)$ and the bottom-right coordinate be $(n,m)$. There are $k$ different colors of pieces, numbered $1 \sim k$. Initially, every cell contains a piece.
There are $q$ operations. Each operation consists of swapping two adjacent (up, down, left, or right) pieces. After this, any sequence of at least $3$ pieces of the same color in the same row or column will be eliminated.
After elimination, all pieces follow gravity and fall down, leaving empty spaces at the top of each column. Once all pieces have finished falling, if a new elimination condition is met, a chain reaction is triggered, continuing until no more eliminations can occur. We call one elimination phase plus one falling phase a "round of elimination," which allows us to define the "number of rounds" triggered by an operation.
Some pieces have special attributes that trigger special effects when eliminated. There are $6$ types:
- 1: Eliminate all pieces in the same row.
- 2: Eliminate all pieces in the same column.
- 3: Eliminate all pieces in the same row and the same column.
- 4: Eliminate all pieces in a $3 \times 3$ square centered at the piece.
- 5: Eliminate all pieces in a $5 \times 5$ square centered at the piece.
- 6: Eliminate all pieces of the same color as the piece.
Triggering a piece's special effect may chain-trigger other pieces' special effects, but these all occur within the same round of elimination (i.e., the chain reaction does not trigger falling).
In the game, every operation must be valid, meaning the two positions are adjacent and neither is empty, and the operation must result in an elimination. If an operation is not valid, it is skipped. The game ends after all $q$ operations.
The "main color" of a valid operation is defined as the color(s) directly eliminated by the swap (excluding eliminations caused by special effects or falling). It is easy to see that a valid operation has at least $1$ and at most $2$ main colors.
Players aim to maximize their score through operations. The scoring rules consist of $5$ parts: Elimination Bonus + Chain Bonus + Combination Bonus + Hand Bonus + Endgame Bonus.
- Elimination Bonus: For each valid operation, the elimination bonus for the $i$-th round is $i$ times the sum of the color numbers of all pieces eliminated in that round.
- Chain Bonus: If a valid operation has a total of $x$ rounds of elimination, the chain bonus is $80(x-1)^2$.
- Combination Bonus: In a single round of elimination, considering only eliminations caused by "at least $3$ consecutive pieces of the same color in a row or column" (i.e., ignoring all eliminations caused by special effects), if a connected component of the same color has size $x$, the combination bonus is $50(x-3)^2$. For example: a $4$-piece line has a bonus of $50$, a $5$-piece line, cross, or T-shape has a bonus of $200$, and a $2 \times 3$ block of the same color has a bonus of $450$.
- Hand Bonus: A hand bonus is calculated every $5$ valid operations. Take the main colors of the previous $5$ valid operations (if an operation has multiple main colors, take the one that yields the maximum bonus according to the rules below) and calculate the bonus based on the following hand rules:
- High Card: $5$ different colors, $50$ points + the largest color number among all cards.
- One Pair: $2$ same colors + $3$ different colors, $100$ points + the color number of the pair $\times 2$.
- Two Pair: $2$ pairs of same colors + $1$ other color, $200$ points + the larger color number of the pairs $\times 2$ + the smaller color number of the pairs.
- Three of a Kind: $3$ same colors + $2$ different colors, $300$ points + the color number of the three $\times 3$.
- Full House: $3$ same colors + $2$ same colors, $500$ points + the color number of the three $\times 3$ + the color number of the two.
- Four of a Kind: $4$ same colors + $1$ other color, $750$ points + the color number of the four $\times 5$.
- Five of a Kind: $5$ same colors, $1000$ points + the color number of the five $\times 10$.
- Endgame Bonus: If all $q$ operations are valid, gain an additional $1000$ points at the end. If the board is completely cleared when the game ends, gain an additional $10000$ points.
Given the initial state of the game and every operation by the player, you need to calculate the player's total score.
Input
Line 1: $4$ positive integers $n, m, k, q$.
Next $n$ lines: $m$ positive integers $a_{i,j}$ each, representing the color of the piece at row $i$, column $j$ in the initial state.
Next $n$ lines: $m$ non-negative integers $b_{i,j}$ each, representing the special effect of the piece at row $i$, column $j$ in the initial state, as described. Specifically, $b_{i,j}=0$ means no special effect.
Next $q$ lines: $4$ positive integers $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$ each, representing the swap of pieces at $(x_{i,1}, y_{i,1})$ and $(x_{i,2}, y_{i,2})$.
Constraints: $n, m \leq 50, k \leq 100, q \leq 1000, a_{i,j} \leq k, b_{i,j} \leq 6, x_{i,1}, x_{i,2} \leq n, y_{i,1}, y_{i,2} \leq m$. It is guaranteed that the initial state has no immediate eliminations.
Output
Output a single non-negative integer representing the total score at the end of the game.
Examples
Input 1
8 8 5 5
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 1 4
3 2 4 2
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8Output 1
11692Note 1
After each operation, the sum of the first $3$ types of bonuses are: $315, 417, 429, 435, 482$. After the $5$th operation, the hand bonus is calculated. The optimal hand is $(1, 2, 4, 2, 4)$, with a bonus of $200 + 4 \times 2 + 2 \times 1 = 210$. Both endgame bonuses are obtained, so the total score is $11692$.
Input 2
8 8 5 8
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0
1 1 2 2
3 2 4 2
3 2 3 3
4 2 4 3
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8Output 2
684Note 2
Compared to the previous example, $3$ invalid operations were added, and the board could not be fully cleared, so no endgame bonus was obtained.
Input 3
5 5 2 1
1 1 2 1 1
1 1 2 1 1
2 2 1 2 2
1 1 2 1 1
1 1 2 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3 4 3Output 3
3023