Problem Background

It is well known that Xiao C is a master at Happy Match-3, while Xiao Z is not very good at games that require a bit of brainpower. During the May Day holiday, Xiao C, feeling bored, decided to teach Xiao Z.

After five days and nights of non-stop teaching, Xiao Z finally grasped the basics (Xiao Z's inner monologue: If only I could show a bit of enthusiasm for probability theory...). However, they both overlooked the fact that this game can be addictive, and more importantly, Xiao Z is from Shandong, so he decided to incorporate some local flavor...

Xiao Z: "…As everyone knows, Texas is in Shandong, so let's call it 'Texas Match-3'!"

Xiao C quickly stopped him, saying, "Come on, you forgot the last mishmash chess game? Besides, this Texas is not that Texas, if you want to do it, do it yourself, don't drag me into it."

Before he could finish, Xiao Z handed over the rules to Xiao C.

Xiao C: "Delicious."

Problem Description

Given a board of size $n \times m$, with the top-left corner at $(1,1)$ and the bottom-right corner at $(n,m)$. There are $k$ different colors of pieces, numbered from $1$ to $k$. Initially, each cell contains a piece.

There are $q$ operations, each involving swapping two adjacent pieces (up, down, left, right). After each operation, any continuous sequence of at least 3 pieces of the same color in a row or column will be eliminated.

After elimination, all pieces will fall due to gravity, leaving the top of the column empty. Once all pieces have fallen, if any new eliminations occur, a chain reaction will continue until no more eliminations are possible. One elimination followed by one fall is defined as a "round of elimination".

Some pieces have special attributes that trigger special effects when eliminated:

• 1. Eliminates all pieces in the same row.
• 1. Eliminates all pieces in the same column.
• 1. Eliminates all pieces in both the same row and column.
• 1. Eliminates all pieces in a $3 \times 3$ square centered on it.
• 1. Eliminates all pieces in a $5 \times 5$ square centered on it.
• 1. Eliminates all pieces of the same color.

Triggering a special effect may chain-trigger other special effects, but these all occur within the same round of elimination (i.e., no additional falls are triggered during the chain reaction).

Each operation in the game must be valid, meaning the two positions are adjacent, neither is empty, and the operation results in piece elimination. If an operation is not valid, it is skipped. After all $q$ operations, the game ends.

A valid operation's "primary color" is defined as the color directly eliminated by the swap (excluding eliminations caused by special effects or falls). It is clear that a valid operation can have at least 1 and at most 2 primary colors.

Players aim to maximize their score through operations. The scoring rules include elimination points, chain points, combo points, hand points, and endgame points.

• Elimination Points: For each valid operation, the elimination points for the $i$-th round of elimination are $i$ times the sum of the color numbers of all eliminated pieces in that round.
• Chain Points: If the total number of elimination rounds for a valid operation is $x$, the chain points are $80(x-1)^2$.
• Combo Points: For each round of elimination, considering only eliminations caused by "at least 3 consecutive same-colored pieces in a row or column" (excluding special effects), if a same-colored connected block of size $x$ is eliminated, the combo points are $50(x-3)^2$. For example: a 4-piece same-color block earns $50$ points, a 5-piece block in a line, cross, or T shape earns $200$ points, and a $2 \times 3$ same-color block earns $450$ points.
• Hand Points: Calculated every 5 valid operations, based on the primary colors of the last 5 operations (if an operation has multiple primary colors, the one that yields the highest points according to the following rules is chosen):
• High Card: All 5 colors are different, earns $50$ points + the highest color number.
• One Pair: 2 same colors + 3 different colors, earns $100$ points + the pair's color number $\times 2$.
• Two Pairs: 2 pairs of same colors + 1 different color, earns $200$ points + the larger pair's color number $\times 2$ + the smaller pair's color number.
• Three of a Kind: 3 same colors + 2 different colors, earns $300$ points + the three-of-a-kind's color number $\times 3$.
• Full House: 3 same colors + 2 other same colors, earns $500$ points + the three-of-a-kind's color number $\times 3$ + the pair's color number.
• Four of a Kind: 4 same colors + 1 different color, earns $750$ points + the four-of-a-kind's color number $\times 5$.
• Five of a Kind: All 5 colors are the same, earns $1000$ points + the five-of-a-kind's color number $\times 10$.
• Endgame Points: If all $q$ operations are valid, an additional $1000$ endgame points are awarded; if the board is completely cleared at the end, an additional $10000$ endgame points are awarded.

Given the initial state of the game and each player's operation, you need to calculate the total score.

Input Format

The first line contains 4 positive integers $n, m, k, q$.

The next $n$ lines, each containing $m$ positive integers $a_{i,j}$, represent the initial colors of the pieces from top to bottom and left to right.

The next $n$ lines, each containing $m$ non-negative integers $b_{i,j}$, represent the special effects of the pieces from top to bottom and left to right. Specifically, $b_{i,j}=0$ means no special effect.

The next $q$ lines, each containing 4 positive integers $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$, represent the coordinates of the pieces to be swapped.

Output Format

Output a single non-negative integer representing the total score at the end of the game.

Sample Input and Output

Input Sample #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 8

Output Sample #1

11692

Input Sample #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 8

Output Sample #2

684

Input Sample #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 3

Output Sample #3

3023

Notes/Hints

[Sample 1 Explanation]

After each operation, the sum of the first 3 types of points is: $315, 417, 429, 435, 482$. After the 5th operation, the best hand is $(1, 2, 4, 2, 4)$, earning $200 + 4 \times 2 + 2 \times 1 = 210$ points. Both endgame points can be earned, so the total score is $11692$.

[Sample 2 Explanation]

Compared to the previous sample, 3 invalid operations are added, and the board cannot be completely cleared, so no endgame points are earned.

[Data Range and 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$.

The initial state guarantees no immediate eliminations.

见题面 Input 部分

见题面 Output 部分