세로 길이가 n, 가로 길이가 m인 직사각형 모양의 격자판이 있습니다. 가장 왼쪽 위 격자의 좌표는 (1, 1)이고, 가장 오른쪽 아래 격자의 좌표는 (n, m)입니다.

각 격자의 양면에는 자연수가 적혀있습니다. 초기 상태에서는 각 격자의 한 면만이 보이도록 놓여 있습니다.

당신은 아래의 행동을 원하는 만큼 수행할 수 있습니다. 행동을 한번 수행할 때마다 비용 k가 소모됩니다.

• 격자판의 하나의 행 혹은 하나의 열에 존재하는 모든 격자를 뒤집어 보이는 면과 숨겨진 면을 교체할 수 있습니다.

모든 행동을 마친 후, (1, 1) 격자에 위치한 말을 (n, m) 격자까지 이동하면서 방문한 격자들의 보이는 수를 점수에 더합니다. 말을 이동할 때는 상하좌우로 인접한 격자로만 이동할 수 있으며, 한번 방문한 격자는 다시 방문할 수 없습니다.

이때, 말을 이동시켜 얻을 수 있는 점수 총합 - 총 비용의 최댓값을 구하려고 합니다.

예를 들어, 아래 그림과 같이 n = 2, m = 2인 격자판이 있고, k = 0이라고 가정해 보겠습니다.

아래와 같이 첫 번째 행과 두 번째 행을 뒤집고 말을 (5 → 7 → 8)과 같이 이동시키면 점수 총합은 20이고 총 비용은 0이며, 이때가 점수 총합 - 총 비용이 최대입니다.

각 격자의 현재 보이는 면에 적힌 수를 나타낸 2차원 정수 배열 visible과, 숨겨진 면에 적힌 수를 나타낸 2차원 정수 배열 hidden이 매개변수로 주어집니다. 점수 총합 - 총 비용의 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ visible의 길이 = n ≤ 14
  
  • 2 ≤ visible[i]의 길이 = m ≤ 100
  • 1 ≤ visible[i][j] ≤ 100
    
• hidden의 길이 = n
  • hidden[i]의 길이 = m
  • 1 ≤ hidden[i][j] ≤ 100
    
  • hidden[i][j]는 visible[i][j]와 같은 격자에 위치한 수입니다.
• 0 ≤ k ≤ 100

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

위와 같이 두 번째 행을 뒤집고 말을 위처럼 이동시키면 점수 총합은 16이고 총 비용은 5이며, 이때가 점수 총합 - 총 비용이 최대입니다. 따라서 11(= 16 - 5)을 return 해야 합니다.