問題
ここは縦横1kmの正方形の小さな島々から創立されたKOMOMO国ある。KOMONO国の領土は縦 h km, 横 w kmの正方形になっていて、h * w分の区画がある。
各島は隣り合っている島が一つもないため、楽に交通できるように、"栄光の架橋"と呼ばれる橋ですべて繋げられている
...はずだったが、近年橋が老朽化して、通ることのできない"栄光の架橋"がいくつかある。
非常に不便だと思ったKOMONO皇太子は、橋を直すことにした。
今、KOMONO皇太子の住んでいる島は非常に交通の便が悪く、なんと橋が一つもかかっていない孤島である。
そこでKOMONO皇太子は一度壊れた橋をすべて撤去して、各島のどれかを出発点とし、できるだけ多くの他の島を訪れて出発点の島まで帰ってこれるように橋を造ることができる島に住もうと考えた。
橋をつくるにあたって、KOMONO国憲法第2081条第1423項より以下の法律が定められている。
1.橋はKOMONO国の領土より外に作ってはならない。
2.橋は 1 kmあたり m YENの建設費を要する。
3.橋は東西または南北にのみ延び、橋が途中で分岐するような構造にしてはならない。必ず一直線である。
ただし、島と島との位置関係により橋が交差してしまうときは、南北に渡る橋を上に、東西に渡る橋を下に建設する。つまり、2本の橋を建設する。
4.橋は島と島との間以外の位置に建設してはならない。
5.橋は南から北、北から南、東から西、西から東の一方通行しかできない。そのため、往復するような場合があったとき、橋は2本分造らなければならない。
橋を新しく造るために積み立てられた予算は p YENである。
予算を超えてしまうとそれ以上橋が架けられなくなってしまう。
KOMONO皇太子が部下に通ることのできる橋の位置と島の位置を表した地図を作らせたらしいので、それを利用して、できるだけほかの多くの島を一度だけ訪れて、出発点の島まで戻ってこられる橋の繋げ方ができる島の数を教えてあげよう。
入力
入力は以下の形式で与えられる。
h w p m a1,1, a2,1...aw,1 a1,2, a2,2...aw,2 . . . a1,h, a2,h...aw,h・地図の縦と横の長さ 1 <= h, w <= 100
・橋の建設の予算 1 <= p <= 1000
・橋1つあたりの建設費 1 <= m <= 1000
・橋と島の状態 0 <= a <= 2
地図は島の位置を2, 壊れていない橋の位置を1, 海を0としているようだ。
壊れていない橋は、東西、南北、東西南北両方の3つの可能性があるが、今回はすべて東西南北両方に延びる橋が2つずつ残っているとする。
出力
出発の島→島たち(できるだけたくさん)→出発の島と橋で繋ぐことのできる島の数の最大値と、そのときの余った予算を空白区切りで出力する。
繋げた島の最大値が複数個あった場合、予算が一番多く残るパターンを出力する。
入出力例
入力例1
5 5 200 10 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2
出力例1
4 80
(2,1)~(4,1)、(1,2)~(1,4)、(5,2)~(5,4)、(2,5)~(4,5)に島と島をつなぐ橋を架ければ、すべての島を繋げることができ、残りの予算は 80 YENとなる。
入力例2
5 5 100 10 2 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 2
出力例2
0 100どうやっても橋と橋をつなぐことができないことがある。
そのときはどこの島とも行き来できないので、行き来できる島の数は0である。使った予算はない。