n が正の整数ならば，n より大きく 2n 以下の素数が1個以上存在する．このことはチェビシェフの定理またはベルトラン・チェビシェフの定理として知られている．ベルトラン(Joseph Louis François Bertrand, 1822–1900)が予想していたことを，1850年にチェビシェフ(Пафнутий Львович Чебышёв, 1821–1894)が証明した．ラマヌジャン(Srinivasa Aiyangar Ramanujan, 1887–1920)は，1919年に公表された論文で，初等的な証明を与えた．エルデシュ(Paul Erdős, 1913–1996)は，1932年に，別の初等的な証明を発見した．

たとえば，10より大きく20以下の素数は 11, 13, 17, 19 で，4個ある． 13より大きく26以下の素数は 17, 19, 23 で，3個ある．

あなたの使命は，与えられた正整数 n に対して，n より大きく 2n 以下の素数を数えるプログラムを書くことである． そのようなプログラムを使うと，個別の正整数に対してチェビシェフの定理が成り立つことを確認できる．

入力はデータセットの並びである． データセットは， ちょうど一つの正整数 n からなる行である． n ≤ 123456 と仮定してよい．

入力の終わりは，1文字のゼロからなる行で示される． これはデータセットではない．

出力は入力データセットと同数の行で構成されなければならない． 各行は一つの整数を含まなければならない． 余計な文字を含んではならない．

整数 n からなるデータセットに対応する出力の整数は，n < p ≤ 2n をみたす素数 p の個数でなくてはならない．

1
10
13
100
1000
10000
100000
0

1
4
3
21
135
1033
8392

世界は絶妙なバランスの上に成り立っている．正と負，光と影，そして左括弧と 右括弧．君には，世界の天秤を監視するために，与えられた文字列の中で括弧が バランスしているかどうかを判定するプログラムを作ってほしい．

与えられる文字列は，丸括弧(“( )”)と角括弧(“[ ]”)の二種類の括弧を含むことがある． 文字列の中で括弧がバランスしているとは，以下が成り立つことである．

• すべての左丸括弧(“(”)には，対応する右丸括弧(“)”)がそれより後にある．
• すべての左角括弧(“[”)には，対応する右角括弧(“]”)がそれより後にある．
• すべての右括弧には，対応する左括弧がある．
• 括弧の対応は一対一でなくてはならず，単一の括弧が複数の括弧と対応す ることはない．
• すべての対応する左括弧と右括弧の組について，その間にある文字列の中で 括弧がバランスしている．

入力は一行または複数の行で構成され，各行は一つのデータセットである． データセットは英文アルファベット，空白，丸括弧(“( )”)と 角括弧(“[ ]”)の二種類の括弧の列で，最後にピリオドがある文字列である． 一行の文字数は100文字以下と仮定してよい． 入力の終わりはピリオドだけからなる行で示されており， この行はデータセットではない．

各データセットについて，括弧がバランスしていれば“yes”を， そうでなければ“no”をそれぞれ1行に出力しなさい． 出力には余分な文字を含んではならない．

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

福岡博士は面白いパネルを発明した． パネルの形は1単位の大きさの正方形で，その表面は黄・桃・赤・紫・緑・青のどれか一色である． そのパネルには次のような注目すべき二つの性質がある． 一つ目は，同じ色のパネルが隣接して配置されると， それらの縁がすこし融けてくっつく性質である． くっついたパネルは，1枚の多角形のパネルになる． 二つ目は パネルに電気ショックを与えるとパネルの色を 6色のうちの任意の1色に変更できる性質である． 色を指定するには電気ショックのパルスの波形を調節すればよい. 既に結合したパネルは電気ショックによりその全体の色が指定された一つの色 に変化する．

彼は，指定した色でパネルを多角形に結合させ， その結合後のパネルの大きさや色の違いによる強度の違いを， 単体のパネルの性質と比較して調べることにした．

図 C-1: パネルと初期配色

多くのパネルを基板の上で複雑な化学プロセスを経て同時に合成し生成するため， 製造したパネルはランダムに着色され， 基板上に長方形の形に並べられている (図C-1)． なお，図C-1中の2個の紫（色4）のパネルは隣接しているので初期状態で既に 一つのパネルに結合されていることに注意されたい．

ある1枚のパネルに電極を装着して，そのパネルの色を最終的な色に 応じて順次変更することにより， 隣接するパネルを段々に合体させて， 指定した色のより大きな結合パネルを得ることができる． 残念ながらパネルに電気ショックを6回与えるとパネルは壊れてしまう． すなわち，色を変えることができる回数は5回である．

図C-1の左上角のパネルに電極を取りつけた場合を考える． 最初にパネルの色を黄色から青色に変えると，右隣のパネルと結合する (図C-2)．

図 C-2: 左上角のパネルの色の変更．黄色 (色1) から青色 (色6) へ．

次に，左上の結合パネルを青色から赤色に変えると赤色の3単位の結合パネルになる (図C-3)． さらに，同パネルを赤色から紫色に変えると，紫色の5単位の結合パネルに なる(図C-4)．

図 C-3: 左上角のパネルの色の変更． 青色 (色6) から 赤色 (色3) へ.

図 C-4: 左上角のパネルの色の変更． 赤色 (色3) から 紫色 (色4) へ.

さらに続けて，紫色を桃色に変更して図C-5の桃色の結合パネルを経て， 桃色を緑色にすると図C-6の緑色の結合パネルが得られる． 緑色の結合パネルは10単位の正方形パネルからなる．

図 C-5: 左上角のパネルの色の変更． 紫色 (色4) から桃色 (色2) へ．

図 C-6: 左上角のパネルの色の変更． 桃色 (色2) から 緑色 (色5)へ．

色々な大きさのパネルの強度を調べるために，指定した色でなるべく大きなパネルを結合したい． あなたの仕事は，指定された色の一番大きな結合パネルを得るための，5回の色の変更方法を見出すプログラムを書くことである．ただし，電極は左上角のパネルに固定されていることとする．

入力は複数のデータセットからなり，それぞれが以下の形式である．

h w c
p_1,1 p_1,2 ... p_1,w
p_2,1 p_2,2 ... p_2,w
...
p_h,1 p_h,2 ... p_h,w

h, wは8以下の正の整数であり，長方形の高さと幅を表す． cは6以下の正の整数であり，最終的に結合されるパネルの目標となる色を表す．p_i,jは6以下の正の整数であり， (i, j)の場所の単位パネルの初期状態の色を表す．入力の終わりは，空白文字1個で区切られた3個のゼロのみからなる行で表される．

各データセットについて，左上角のパネルの5回の色変更により，目標色となる左上角のパネルの最大の大きさが何単位にあたるかを1行に出力せよ．それ以外の余計な文字を含んではいけない．

3 5 5
1 6 3 2 5
2 5 4 6 1
1 2 4 1 5
4 5 6
1 5 6 1 2
1 4 6 3 2
1 5 2 3 2
1 1 2 3 2
1 1 5
1
1 8 6
1 2 3 4 5 1 2 3
8 1 1
1
2
3
4
5
1
2
3
8 8 6
5 2 5 2 6 5 4 2
4 2 2 2 5 2 2 2
4 4 4 2 5 2 2 2
6 4 5 2 2 2 6 6
6 6 5 5 2 2 6 6
6 2 5 4 2 2 6 6
2 4 4 4 6 2 2 6
2 2 2 5 5 2 2 2
8 8 2
3 3 5 4 1 6 2 3
2 3 6 4 3 6 2 2
4 1 6 6 6 4 4 4
2 5 3 6 3 6 3 5
3 1 3 4 1 5 6 3
1 6 6 3 5 1 5 3
2 4 2 2 2 6 5 3
4 1 3 6 1 5 5 4
0 0 0

10
18
1
5
6
64
33

有名な一人遊びゲームの作家であるソリタリウス氏は，今日もまた新しいアイデアを思いついた． ソリタリウス氏の新しいゲームでは，さまざまな色と大きさの平らな円盤を使う．

まず最初に，全部の円盤をテーブル中央付近にばらまく． 別の円盤が上に重なっていない円盤の中に同じ色のものが2枚あれば，それらを同時に取り除くことができる． なお，円盤同士が1点で接しているだけなら，それらを重なっているとはみなさない．

図 D-1: テーブル上の7枚の円盤

たとえば，図 D-1 の場合，まず最初に取り除けるのは2枚の黒い円盤だけである． これらを取り除くことで，今度は2枚の白い円盤を取り除けるようになる． しかし，グレーの円盤は決して取り除くことができない．

この問題では，与えられた円盤の色，大きさ，初期の位置関係から，最大何枚の円盤を取り除くことができるか計算するプログラムを作成して欲しい．

入力は複数のデータセットからなり，それぞれが以下のような形式でテーブル上に円盤をばらまいた直後の状態を表す．

n
x₁ y₁ r₁ c₁
x₂ y₂ r₂ c₂
...
x_n y_n r_n c_n

最初の行のnは円盤の枚数を表す正整数である． 続くn行は，それぞれが空白文字1個で区切られた4個の整数からなり，n枚の円盤の色，大きさ，初期の位置関係を次のように表す．

• (x_i, y_i), r_i, c_i はi番目の円盤の中心のxy座標，半径，色番号をそれぞれ表し，
• i番目の円盤がj番目の円盤の上に重なるときには，必ずi < jが成り立つ．

色番号は1以上4以下であり，一つのデータセット中に同じ色の円盤は高々6枚しか出現しないと仮定して良い． また，円盤の中心のxy座標は常に0以上100以下，半径は常に1以上100以下と仮定して良い．

入力の終わりは1個のゼロで示される．

各データセットについて，取り除ける円盤の最大枚数をそれぞれ1行に出力しなさい．

4
0 0 50 1
0 0 50 2
100 0 50 1
0 0 100 2
7
12 40 8 1
10 40 10 2
30 40 10 2
10 10 10 1
20 10 9 3
30 10 8 3
40 10 7 3
2
0 0 100 1
100 32 5 1
0

2
4
0

あなたが勤める電力会社は，この春，電力需給逼迫により「輪番停電」を実施した．これはサービス地域をいくつかのグループに分け，また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

あなたは北九州で客先の要望に応じて番犬を派遣する会社を経営している． あなたの会社の特徴は，現場に番犬の効果を高めるフェンスを設置するところである．

犬は長いロープの先端に繋がれていて，ロープの他端は杭で固定されている．犬が到達できる境界のところにフェンスを設置して，フェンスに近づくよそ者がいたら犬が対応するようにする．

周辺には1つだけ，長方形の建物があってもよい．犬は建物には入れないが，ロープの長さが許す範囲で建物を回り込んで動くことはできる (図F-1)．建物の壁面に沿った部分にはフェンスは不要である．

ロープの長さと建物の位置と大きさを受け取り， フェンスの長さを計算するプログラムを作れ．

入力は複数のデータセットからなり，1つのデータセットは次の形式の1行で表される5つの整数からなる．

len x₁ y₁ x₂ y₂

len はロープの長さを表し， x₁, y₁, x₂, y₂は建物の位置と大きさを表す． 座標(x,y)の点は， x₁ < x <x₂かつy₁ < y < y₂のとき建物の内側にある．つまり建物の外壁はX軸またはY軸に平行である． 杭は原点に置かれている．

0 < len ≤ 100, −100 ≤ x₁ < x₂ ≤ 100, −100 ≤ y₁ < y₂ ≤ 100 であるものとしてよい． さらに，杭は建物から離れていることを仮定してよい (つまり，杭は建物の内側になく，かつ壁に接してもいない)．

入力の終わりは5つのゼロからなる行によって示される．

各入力ごとに，フェンスの長さの合計を小数点つき数として出力せよ．出力には数値以外の文字があってはならない．出力には0.00001を超える誤差があってはならない．

3 3 0 6 5
5 3 0 6 5
6 3 0 6 5
7 3 0 6 5
9 3 0 6 5
10 3 0 6 5
12 3 0 6 5
100 3 0 6 5
4 -3 4 5 8
5 -3 4 5 8
6 -3 4 5 8
64 -30 40 50 50
7 -3 4 5 8
10 -3 4 5 8
11 -3 4 5 8
14 -3 4 5 8
35 -3 4 5 8
100 -3 4 5 8
10 5 9 12 12
13 5 9 12 12
15 5 9 12 12
18 5 9 12 12
19 5 9 12 12
20 5 9 12 12
21 5 9 12 12
100 5 9 12 12
100 -5 1 -3 5
100 0 1 100 2
100 -1 99 100 100
10 -1 1 1 2
84 1 -77 5 -42
27 -12 -7 3 -4
0 0 0 0 0

18.84955592
26.77945045
31.69103413
39.54501577
55.51851918
63.83954229
75.38181750
628.05343108
25.13274123
24.98091545
29.43519428
318.90944272
35.02723766
55.44758990
64.23914179
89.33649537
219.11188064
627.48648370
62.83185307
76.33420961
88.61222855
112.17417345
121.59895141
126.16196589
132.25443447
628.23333565
628.18890261
626.17695473
613.16456638
62.61625003
527.84509612
168.07337509

正方形の部屋を縦横に並べた長方形領域の迷路がある．この迷路は出入口を除いて壁で囲まれている．迷路の入口は長方形の上辺の最も左側で，つまり最上段の最左の部屋の上辺は開いている．出口は同様に下辺の最も右側にある．

迷路の中で，ある部屋と縦または横に隣り合う部屋との間には壁があり，カードキーで開けられるドアが1つあるか全くドアがないかのどちらかである．ドアがある場合は，カードを1枚入れるとドアが開いて通り抜けることができるが，ドアはすぐに閉まり，カードは返却されない．カードは1種類でどこのドアでも使うことができる．ドアがない壁を通り抜けることはできない．

迷路の地図が与えられた時に，カードが何枚あれば入口から出口に抜けられるかを求めるのは簡単な問題だろう．図G-1の場合は，図G-2の緑の矢印()の経路を辿れば，10枚のカードで抜けられることが分かる．

図 G-1: 迷路の地図

図 G-2: 最短経路

迷路中のドアが一箇所だけ故障していて通れなくなっていることが分かった． どこのドアが故障しているかの情報はない．壊れたドアにカードを入れるとカードは直ちに返却される．ドアの故障は見ただけでは分からない．

図 G-3: 通り抜けられなくなる可能性のある迷路

図G-3の場合，故障しているドアが赤いバツ印() の位置のドアの場合は入口から出口に行けなくなるが，図G-1の迷路では故障しているドアがどれであっても，入口から出口に行くことはできる．図G-1 の迷路で，図G-2の最短経路を行こうとして図G-4の赤いバツ印のドアが故障していることを発見した場合，緑の矢印の経路で出口にたどり着くことになるだろう．この場合，カードは20枚必要になる．

図 G-4: ドアが故障した迷路

しかし，この迷路はもっと少ない枚数のカードで抜けることができる．まず，ドアの故障を見つけるまでは図G-5の経路にしたがって進む．これは故障がなくても12枚のカードが必要なので最短経路ではない．経路の途中で故障しているドアを見つけたら，そこからそのドアを使わないときの出口への最短経路で進む．この戦略ならば故障しているドアがどこであっても16枚のカードで抜けることができる．この戦略で最悪となる16枚のカードが必要なケースを図G-6に示す．

図 G-5: 故障発見前の経路

図 G-6: 16枚のカードが必要な例

迷路の地図を与えられた時に，故障したドアがどこであっても迷路を抜けることのできるカードの枚数の最小値を答えるプログラムを作成しなさい．

入力はそれぞれが迷路を表すひとつ以上のデータセットからなる．データセット数は100以下である．

データセットの最初の行には迷路の高さ hと幅 w を与えるふたつの整数値がこの順に入っている．2 ≤ h, w ≤ 30 であるものとしてよい．

それに続く 2 × h − 1 行は，隣接する部屋の間のドアの有無を示している．最初の行の先頭は空白で，その後には w − 1 個の 1 または 0 が空白ひとつで区切られて並んでいる．これらは一番上の行の横に隣り合う部屋の間のドアの有無を示すものである．1 はドアがないことを，0 はあることを意味する． 次の行の先頭には空白はなく，w 個の 1 または 0 が空白ひとつを区切りに続く．これらは最初と次の行の縦に隣り合う部屋の間のドアの有無を表す．整数 0/1 はドアの有/無を示す．引き続く行は交互に横と縦に隣り合う部屋の間のドアの有無を同様に表す．

入力の終わりはふたつのゼロを含む行で表される．

各データセットについて，必要なカードの枚数の最小値を表す整数ひとつを持 つ行を出力せよ．また，故障しているドアによって入口から出口へ行く経路がなくな る可能性のある場合は −1 を出力せよ．出力行にはこの数値以外の文字を 含んではならない．

4 8
 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
 0 0 0 0 1 0 0
0 1 1 1 1 0 0 0
 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
 0 0 0 0 0 1 0
4 8
 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
 0 0 0 0 1 0 0
0 1 1 1 1 0 0 0
 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
 0 0 0 0 0 0 1
2 2
 0
0 0
 0
3 3
 0 0
0 1 0
 0 1
0 0 0
 0 0
2 4
 1 0 1
0 0 0 0
 0 1 0
6 12
 0 0 0 1 1 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 1 1 0
 1 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 1 0 0 1 1 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 1 0 0 1 1 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 1 1 0 0
0 0 0 0 0 1 1 0 0 1 0 0
 1 0 0 0 0 0 0 1 0 0 0
20 20
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0

16
-1
4
10
-1
32
40