005 - 輪番停電計画

あなたが勤める電力会社は，この春，電力需給逼迫により「輪番停電」を実施した．これはサービス地域をいくつかのグループに分け，また1日をいくつかの時間帯に分け，各時間帯で順に1つのグループを停電させるものであった．つまり停電していないグループの電力需要の合計が供給力を超えないようにすることで，予測不能の大規模停電を回避したのであった．

当時カスタマーセンター担当だったあなたは，この輪番停電に対する山のような苦情を聞くにつけ，もう少し良い方法があったのではないかと思うようになった．苦情の多くは頻繁な停電についてだった．これに対しては，グループの数を増やすことによって各グループの停電の頻度を減らせたはずだ．他に多かった苦情には，グループ分けが分かりにくく(実際フラクタルに分けたとまで揶揄されていた)，どの町がどのグループに所属しているかは会社が公表した表を精査しない限りは分からないというのもあった．サービス地域が長方形で，その中に町が格子状に並んでいることを考えれば，もっと分かりやすいグループ分けができたはずだ．

このことを社長に直訴したところ，この夏再びの輪番停電の際のグループ分けはあなたが行うことになってしまった．口は災いの元，とんでもない仕事をしょいこんでしまった．とにかく，供給力に収まる範囲内でなるべく多数のグループに分けなければいけない．さらにグループ分けも分かりやすくなるようにしなければならない．

あなたの使命は，需要表(町ごとの電力需要が書かれた表)と供給力をもとに，次の条件を満たすようなグループ分けを行うプログラムを作ることである．

1. グループ分けは地域を水平または垂直に分割することを再帰的に行ってできるものとする．つまり，グループ分けとはサービス地域全体のみを要素とする集合に次の分割手順を0回以上適用した結果できる地域の集合だとする:

   (分割手順) 集合から1つの地域を取り除き，それを水平または垂直方向に2つの小地域に分割し，それらを集合に追加する．

2. グループ分けの最大抑制需要 — つまり任意の1グループを停電させたときの残りのグループの需要の合計の最大値 — は供給力を超えてはならない．
3. グループ分けに含まれるグループ数は，上記1, 2の条件を満たすグループ分けの中で最大でなければならない．
4. グループ分けは上記1, 2, 3の条件を満たすグループ分けの中で最大の予備力を持たなければならない．グループ分けの予備力とは，供給力と最大抑制需要の差である．

なお，条件1は図E-1のようなグループ分けを許さないことに注意せよ．

図E-1: 条件1を満たさないグループ分け

入力は1つ以上のデータセットからなる．1つのデータセットは次の形式をしている．

h w s
u₁₁ u₁₂ ... u_1w
u₂₁ u₂₂ ... u_2w
...
u_h1 u_h2 ... u_hw

先頭行は3つの正の整数h, wおよびsからなり，それぞれ需要表の高さ，幅，および供給力を表す．続くh行にはそれぞれw個の整数があり，その位置にある町の需要を表している．これらの数は以下の範囲の値をとる．

1 ≤ h, w ≤ 32
1 ≤ u_ij ≤ 100

遺憾ではあるが，供給力は地域全体の消費電力の合計よりも小さいと仮定してよい．

最後のデータセットの次の行はゼロが3つある行である．

各データセットについて，条件を満たすようなグループ分けに含まれるグループ数と予備力を1行に出力せよ．各行はこれらの数と区切りの空白1文字以外を含んではならない．

3 3 33
4 4 2
2 9 6
6 5 3
3 4 15
1 2 1 2
2 1 2 1
1 2 1 2
32 32 1112
1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
2 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 2 1 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1
2 1 1 1 1 1 1 1 2 1 1 1 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 2 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0

4 1
6 0
553 0