오미노박스

악당 마법사가 도시 한가운데에 폭탄을 설치하고 타이머를 걸어 두었다. 폭탄 옆에는 키패드와 퍼즐이 함께 놓여 있고, 퍼즐의 답을 입력하면 폭탄이 멈춘다. 퍼즐의 이름은 오미노박스다.

오미노박스는 단위 정육면체가 얼마간 들어 있는 상자 하나와, 가능한 N-오미노를 전부 하나씩 모은 조각 모음으로 이루어진다. 조각을 하나씩 상자 안에 떨어뜨려 점수를 얻고, 이렇게 얻는 점수의 합이 가장 클 때의 값이 오미노박스의 답이다.

N-오미노는 변끼리 맞닿게 이어 붙인 단위 정사각형 $N$개의 모임이다. 1-오미노는 단위 정사각형 하나이고, N-오미노는 (N-1)-오미노에 변이 맞닿는 단위 정사각형 하나를 더 붙인 모양이다. 평행이동만으로 겹치는 두 조각은 같은 조각이고, 회전하거나 뒤집어야 겹치는 두 조각은 서로 다른 조각으로 센다. 아래 그림은 3-오미노 6개 전부와 4-오미노 19개 중 일부다.

상자의 바닥은 $R \times C$ 격자이고 네 벽의 높이는 $H$다. 격자의 칸 $(i, j)$에는 단위 정육면체가 $H_{ij}$개 쌓여 있고, 쌓인 정육면체는 옮길 수 없다.

조각은 격자에 맞춰 상자 위에 올린 다음 그대로 떨어뜨린다. 조각을 회전하거나 뒤집는 것은 허용되지 않고, 조각 전체가 바닥 격자 안에 들어가야 한다. 조각은 쌓인 정육면체나 바닥에 닿을 때까지 내려간다. 즉 조각이 덮는 칸들의 $H_{ij}$ 중 최댓값을 $t$라 하면 조각의 아랫면은 높이 $t$에 놓이고, 이때 얻는 점수는 조각의 아랫면에서 상자 위쪽 테두리까지의 거리 $H - t$다. 점수를 적은 뒤에는 조각을 다시 꺼내므로 상자 안 정육면체 배치는 끝까지 그대로다. 바닥 격자 안에 놓을 자리가 아예 없는 조각의 점수는 0이다.

조각을 하나씩 가장 좋은 자리에 떨어뜨렸을 때 얻는 점수의 합, 즉 오미노박스의 답을 구하라.

첫 줄에 도전 과제의 수 $T$가 주어진다 ($1 \le T \le 200$).

이어서 $T$개의 도전 과제가 주어진다. 각 도전 과제의 첫 줄에는 네 정수 $R$, $C$, $H$, $N$이 주어진다 ($1 \le R, C, H \le 30$, $1 \le N \le 10$). 상자 바닥은 $R \times C$ 격자이고, 벽의 높이는 $H$, 조각의 크기는 $N$이다. 다음 $R$개 줄에는 각각 $C$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 칸 $(i, j)$에 쌓인 정육면체의 수 $H_{ij}$다 ($0 \le H_{ij} \le H$).

각 도전 과제마다 오미노박스의 답을 한 줄에 출력한다.