순환 정전 계획

전력 수급 균형이 심각하게 빠듯해지자, 당신이 근무하는 전력 회사는 이번 봄에 순환 정전을 시행했다. 회사는 서비스 지역을 여러 개의 마을 그룹으로 나누고, 하루를 여러 개의 정전 시간대로 나누었다. 각 정전 시간대마다 그룹 하나가 — 한 그룹에서 다음 그룹으로 번갈아 가며 — 전력 공급을 차단당한다. 나머지 마을들이 사용하는 전력 총수요를 공급 용량 이내로 유지함으로써, 회사는 예측할 수 없는 대규모 정전을 피할 수 있었다.

고객 상담 부서에서 일하던 당신은 수많은 불만을 들어야 했고, 더 나은 방식이 가능하겠다고 생각하게 되었다. 대부분의 불만은 잦은 정전에 관한 것이었는데, 지역을 더 많은 그룹으로 나누면 각 그룹의 정전 빈도를 낮출 수 있다. 다른 불만은 복잡한 그룹 구성에 관한 것이었다(어떤 사람은 그룹의 모양이 프랙탈 같다고까지 말했다). 이 때문에 공개된 목록을 꼼꼼히 살펴보지 않고서는 어느 마을이 어느 그룹에 속하는지 알기 어려웠다. 서비스 지역이 직사각형이고 마을들이 격자 형태로 배치되어 있으므로, 당신은 훨씬 단순한 그룹 구성이 가능하다고 믿는다.

이 분석을 회사 사장에게 직접 이야기하자, 당신은 이번 여름의 순환 정전 계획을 맡게 되었다. 총수요를 공급 용량 이내로 유지하면서 서비스 지역을 가능한 한 많은 그룹으로 나누어야 하며, 그룹은 단순하고 기억하기 쉬워야 한다.

수요 표(각 마을의 전력 수요를 나타낸 표)와 공급 용량이 주어질 때, 다음 조건을 모두 만족하는 마을 그룹 구성을 구하는 프로그램을 작성하라.

1. 그룹 구성은 지역을 가로 또는 세로로 반복해서 쪼개어 만든다. 즉, 전체 지역 하나만을 담은 집합에서 시작하여 다음 절차를 0번 이상 반복해서 얻어야 한다: 집합에서 영역 하나를 꺼내어 세로 또는 가로로 두 개의 부분 영역으로 나눈 뒤, 두 부분 영역을 집합에 다시 넣는다. (이것을 길로틴(guillotine) 분할이라고 한다.)
2. 그룹 구성의 최대 억제 수요, 즉 한 그룹을 제외한 나머지 모든 그룹의 총수요가 가질 수 있는 최댓값이 공급 용량 이하여야 한다.
3. 조건 1과 2를 만족하는 그룹 구성 중에서 그룹의 개수가 가장 많아야 한다.
4. 조건 1, 2, 3을 만족하는 그룹 구성 중에서 예비 전력이 가장 커야 한다. 여기서 예비 전력이란 공급 용량과 최대 억제 수요의 차이다.

조건 1은 그림 E-1과 같은 그룹 구성을 허용하지 않는다는 점에 유의하라.

그림 E-1: 조건 1을 위반하는 그룹 구성

입력은 하나 이상의 데이터셋으로 구성된다. 각 데이터셋은 다음 형식으로 주어진다.

h w s
u11 u12 ... u1w
u21 u22 ... u2w
...
uh1 uh2 ... uhw

첫 번째 줄에는 세 양의 정수 $h$, $w$, $s$가 주어지며, 각각 수요 표의 높이와 너비, 그리고 전력 공급 용량을 나타낸다. 이어지는 $h$개의 줄에는 각각 $w$개의 정수가 주어지며, $u_{ij}$는 $i$행 $j$열에 위치한 마을의 수요다. 이 값들은 다음을 만족한다.

• $1 \le h, w \le 32$
• $1 \le u_{ij} \le 100$

공급 용량은 전체 지역의 총수요보다 반드시 작다고 가정해도 된다.

입력의 끝은 세 개의 0으로 이루어진 줄로 표시된다.

각 데이터셋에 대해, 조건을 만족하는 그룹 구성의 그룹 개수와 예비 전력을 두 정수로 한 줄에 출력한다. 두 수는 공백 하나로 구분하며, 그 외의 다른 문자는 출력하지 않는다.