금연 부탁드립니다

금연법이 시행되면서 거의 모든 식당은 흡연 손님과 비흡연 손님을 서로 다른 구역에 앉힐 수 있도록 내부 구조를 바꿔야 했습니다.

식당 주인 요한(Johann)은 자신의 식당을 두 개의 구역으로 나누고, 두 구역을 에어록(air lock)으로 연결하기로 했습니다. 직원은 흡연 구역에 들어갈 수 없으므로, 각 에어록에는 음식을 건네줄 수 있는 해치(hatch)도 함께 설치합니다. 흡연 구역은 바깥과 바로 연결해 난방비를 아끼고 신선한 공기를 공급하며, 비흡연 구역은 직원이 음식을 낼 수 있도록 주방과 연결되어야 합니다.

식당은 크기가 모두 같은 정사각형 방들로 이루어진 직사각형 격자입니다. 각 방은 (최대 네 개의) 이웃한 방과 통로로 연결될 수 있습니다. 식당을 두 구역으로 나누기 위해, 요한은 두 방을 잇는 통로 중 일부에 에어록을 설치합니다.

비용은 다음과 같습니다.

• 에어록은 설치되는 통로의 넓이 1제곱미터당 1000유로입니다.
• 각 에어록에는 해치가 하나씩 필요하며, 해치 하나는 1000유로입니다.

즉, 넓이가 $a$ 제곱미터인 통로에 에어록을 설치하는 비용은 $1000 \cdot a + 1000$ 유로입니다. 통로가 없는 벽(넓이 0)은 에어록도 해치도 필요 없으므로 비용이 들지 않습니다.

입구와 연결된 방은 흡연 구역에, 주방과 연결된 방은 비흡연 구역에 속해야 합니다. 흡연 구역의 방과 비흡연 구역의 방을 잇는 모든 통로에는 에어록(과 해치)을 설치해야 하며, 한 구역 안에만 있는 통로에는 아무것도 설치하지 않아도 됩니다.

전체 비용이 최소가 되도록 식당을 두 구역으로 나누는 것을 도와주세요.

첫째 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 주어집니다. 각 테스트 케이스는 다음과 같이 주어집니다.

• 방의 행 수와 열 수를 나타내는 두 양의 정수 $nr$, $nc$ ($nr, nc < 1000$).
• 입구와 연결된 방의 행과 열을 나타내는 두 정수 $er$, $ec$ ($0 \le er < nr$, $0 \le ec < nc$).
• 주방과 연결된 방의 행과 열을 나타내는 두 정수 $kr$, $kc$ ($0 \le kr < nr$, $0 \le kc < nc$).
• $nr$개의 줄. 각 줄에는 100 미만의 음이 아닌 정수 $nc - 1$개가 있습니다. $i$번째 줄의 $j$번째 정수는 방 $(i, j)$와 방 $(i, j+1)$ 사이 통로의 넓이(제곱미터)입니다.
• $nr - 1$개의 줄. 각 줄에는 100 미만의 음이 아닌 정수 $nc$개가 있습니다. $i$번째 줄의 $j$번째 정수는 방 $(i, j)$와 방 $(i+1, j)$ 사이 통로의 넓이(제곱미터)입니다.

넓이가 0이면 두 방 사이에 통로가 없다는 뜻입니다(막힌 벽).

각 테스트 케이스마다, 입구와 연결된 방이 흡연 구역에, 주방과 연결된 방이 비흡연 구역에 속하도록 식당을 두 구역으로 나눌 때의 최소 총비용(유로)을 한 줄에 출력합니다.