問題
或る島、錠峰島。
其の島では、二人の神が支配を行っていた。
大地を統べる神『威』、そして天を統べる神『火狸』。
彼らは其の力で錠峰島の人々を支配していた。
或る日、彼らの支配から脱しようとする男が現れた。
其の男は、『仏弐倶』と呼ばれる。
彼は現在の地点から島の或る場所の空港に向かい、
其処から新たなる世界へ飛び立とうとしている。
だが、神々が易々と彼を逃がす筈も無い。
威は大地を肆*肆の壱拾六個の小島の集合に分断した。
仏弐倶は、現在の島から上下左右の方向にある島に移動でき、其の際に生命力を壱消費する。
火狸は幾つかの小島に強烈な一撃、『聖雷』を喰らわそうとしている。
此れを喰らうと、強い精神支配を受けてしまう為避けなければならない。
しかし仏弐倶は、独自に開発した『状態反転装置』を持っていた。
此れを使うと、彼の現在地から上下左右壱マスにある全ての島の『聖雷の有無』を切り替えることができる。
或る島を指定して反転させることはできず、必ず上下左右全ての島の状態は反転する。
彼は此の道具を用いて脱出を試みるが、状態反転装置は使用者の生命力を消耗する欠点があった。
状態反転装置の使用に必要な生命力と、仏弐倶か脱出を始めた瞬間の島の情報が与えられるので、
彼が空港に辿り着くまでに消費しなければならない生命力の最小値を出力するプログラムを作成して欲しい。
入出力形式
入力
壱行目に、状態反転装置を使用する際に消費する生命力 N が与えられる。
次の行から、脱出開始時の島の情報が肆行×肆文字に渡って与えられる。
島の情報は以下の肆つに分けられる。
なお、脱出開始時の仏弐倶の初期位置と空港の位置は聖雷は存在しないことが保障される。
. -> 聖雷が降っていない土地。 # -> 聖雷が降っている土地。 S -> 仏弐倶の初期位置。 G -> 空港の位置。
出力
仏弐倶が空港に辿り着くまでに消費しなければならない生命力の最小値を改行込みで出力せよ。
制約
- Nは整数である。
- 0 ≦ N ≦ 891
入出力例
例壱
入力
3 S... ###. .... G...
出力
6
例弐
入力
8 S... ###. .... G...
出力
9
次に脱出するのは君だ。