선과 포커의 결합

$n \times m$ 크기의 보드가 주어진다. 왼쪽 위 칸은 $(1, 1)$, 오른쪽 아래 칸은 $(n, m)$이다. 조각의 색은 $1$부터 $k$까지 $k$가지가 있으며, 처음에는 모든 칸에 조각이 하나씩 놓여 있다.

연산은 총 $q$번 주어진다. 각 연산은 상하좌우로 인접한 두 조각을 서로 바꾼다. 그다음 같은 행이나 같은 열에서 같은 색 조각이 3개 이상 연속으로 이어진 부분을 모두 제거한다.

제거가 끝나면 중력에 따라 조각이 아래로 떨어지고, 각 열의 위쪽에 빈칸이 생긴다. 모든 조각이 떨어진 뒤에도 제거할 수 있는 조각이 남아 있으면 연쇄 반응이 일어나, 더 이상 제거할 것이 없을 때까지 계속된다. 한 번의 제거와 한 번의 낙하를 합쳐 '한 라운드'라고 부른다. 연산 하나가 일으키는 라운드 수를 그 연산의 '라운드 수'라고 한다.

일부 조각은 제거될 때 특수 효과를 발동하는 특수 속성을 가진다. 특수 속성은 6가지다.

• 제거되면 같은 행의 모든 조각이 제거된다.
• 제거되면 같은 열의 모든 조각이 제거된다.
• 제거되면 같은 행과 같은 열의 모든 조각이 제거된다.
• 제거되면 자신을 중심으로 한 $3 \times 3$ 정사각형 안의 모든 조각이 제거된다.
• 제거되면 자신을 중심으로 한 $5 \times 5$ 정사각형 안의 모든 조각이 제거된다.
• 제거되면 같은 색의 모든 조각이 제거된다.

특수 효과는 다른 조각의 특수 효과를 다시 발동시킬 수 있다. 이 모든 일은 같은 라운드 안에서 연쇄적으로, 중력에 의한 낙하 전에 일어난다.

연산이 유효하려면 두 위치가 인접해 있고, 둘 다 비어 있지 않으며, 교환으로 최소 한 번의 제거가 일어나야 한다. 유효하지 않은 연산은 건너뛴다. 게임은 $q$번의 연산을 모두 처리하면 끝난다.

유효한 연산의 주색은 교환으로 직접 제거되는 색을 말한다. 특수 효과나 낙하로 제거된 조각은 포함하지 않는다. 유효한 연산의 주색은 1가지 또는 2가지다.

플레이어는 제거 점수, 연쇄 점수, 조합 점수, 패턴 점수, 종료 점수의 다섯 가지 점수를 얻는다.

• 제거 점수: 유효한 연산의 $i$번째 라운드 제거 점수는, 그 라운드에서 제거된 모든 조각의 색 번호 합에 $i$를 곱한 값이다.
• 연쇄 점수: 유효한 연산의 총 라운드 수가 $x$이면, 연쇄 점수는 $80 \cdot (x - 1)^2$이다.
• 조합 점수: 한 라운드에서 같은 행이나 열에 같은 색이 3개 이상 연속으로 놓여 제거된 경우만 본다. 특수 효과로 제거된 것은 제외한다. 변으로 연결된 같은 색 덩어리의 크기가 $x$이면, 조합 점수는 $50(x-3)^2$이다. 예를 들어 한 줄에 4개가 놓이면 $50$점이다. 한 줄, 십자형, T자형으로 5개가 놓이면 $200$점이다. 낙하 후 생길 수 있는 $2 \times 3$ 크기의 같은 색 덩어리는 $450$점이다.
• 패턴 점수: 유효한 연산 5회마다, 직전 5회 연산의 주색으로 패턴 점수를 계산한다. 연산에 주색이 2가지 있으면, 점수가 더 높아지는 쪽을 택한다. 규칙은 다음과 같다.
  • 하이카드: 5가지 색이 모두 다르다. 점수는 $50$에 가장 큰 색 번호를 더한 값이다.
  • 원 페어: 같은 색 2개와 다른 색 3개다. 점수는 $100$에 페어 색 번호의 $2$배를 더한 값이다.
  • 투 페어: 두 쌍의 페어와 다른 색 1개다. 점수는 $200$에 큰 쪽 페어 색 번호의 $2$배와 작은 쪽 페어 색 번호를 더한 값이다.
  • 쓰리 오브 어 카인드: 같은 색 3개와 다른 색 2가지다. 점수는 $300$에 트리플 색 번호의 $3$배를 더한 값이다.
  • 풀하우스: 같은 색 3개와 다른 색 2개다. 점수는 $500$에 트리플 색 번호의 $3$배와 페어 색 번호를 더한 값이다.
  • 포 오브 어 카인드: 같은 색 4개와 다른 색 1개다. 점수는 $750$에 포 색 번호의 $5$배를 더한 값이다.
  • 파이브 오브 어 카인드: 5개가 모두 같은 색이다. 점수는 $1000$에 그 색 번호의 $10$배를 더한 값이다.
• 종료 점수: $q$번의 연산이 모두 유효하면 $1000$점을 보너스로 받는다. 게임이 끝났을 때 보드가 완전히 비어 있으면 $10\,000$점을 보너스로 받는다.

초기 상태, 특수 속성, 각 연산이 주어졌을 때 플레이어의 총점을 구하라.

첫 줄에 네 정수 $n$, $m$, $k$, $q$가 주어진다 ($2 \leq n, m \leq 50$; $m + n > 4$; $2 \leq k \leq 100$; $1 \leq q \leq 1000$).

다음 $n$개 줄에는 각각 $m$개의 정수 $a_{i,j}$가 주어진다. 위에서 아래, 왼쪽에서 오른쪽 순서의 초기 색이다 ($1 \leq a_{i,j} \leq k$).

그다음 $n$개 줄에는 각각 $m$개의 정수 $b_{i,j}$가 주어진다. 초기 특수 속성이며, $0$은 특수 속성이 없음을 뜻한다 ($0 \leq b_{i,j} \leq 6$).

마지막 $q$개 줄에는 각각 네 양의 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. $(x_1, y_1)$의 조각과 $(x_2, y_2)$의 조각을 서로 바꾸라는 뜻이다 ($1 \leq x_1, x_2 \leq n$; $1 \leq y_1, y_2 \leq m$).

초기 상태에서는 바로 제거가 일어나는 상황이 없다.

게임이 끝났을 때의 총점을 나타내는 정수를 한 줄에 출력한다.

각 연산 후 처음 세 종류 점수의 합은 차례로 $315$, $417$, $429$, $435$, $482$이다. 5번째 연산 후에 패턴 점수를 계산한다. 최적의 패턴은 $(1\ 2\ 4\ 2\ 4)$이며, 점수는 $200 + 4 \cdot 2 + 2 \cdot 1 = 210$이다. 게임이 끝나면 두 종류의 종료 보너스를 모두 받아 총점은 $11\,692$이다.