お祭りを邪魔する子は、お仕置きです！

アラタ

先生！魍魎ズとアラタが神木祭を台無しにする前に、止めなければいけません！ここで戦うと花火に火がつくかもしれないので……修行部の皆さんに手伝っていただいて、ロープでアラタを捕まえようと思います。

広場は $N \times N$ のマス目になっています。私は今、$1$ 行 $1$ 列のマスの中心にいて、アラタは広場のどこかのマスの中心にいます。皆さんに手伝っていただけば、マスの中心から隣のマスの中心へ移動しながらロープを置けそうです。修行部の皆さんは、上下左右に隣接するマスにだけ移動できます。

修行部の皆さんが $1$ 行 $1$ 列から出発し、合計 $K+1$ 個のマス $P_0$, $P_1$, $\cdots$, $P_K$ を順に訪れたとします。

• $P_0$ は出発点の $1$ 行 $1$ 列です。
• $P_K$ はアラタのいるマスです。

ここでは、ロープを構成する線分の本数、つまり $K$ をロープの長さと定義します。

アラタをロープで捕まえたら、私はすぐにロープを引っ張って回収しなければなりません。でも、曲がっているところが多いほど引っかかってしまい、引っ張るのに大きな力が必要になります。力がかかると回収が遅れ、その間にアラタが逃げたり、状況がさらに危険になったりするかもしれないので、力の合計も最小にしたいんです。

現在のロープを構成する点が $P_0$, $P_1$, $\cdots$, $P_i$ のとき、ロープを一度引っ張ると、次のことが起こります。

• 端点 $P_i$ が取り除かれ、残った点 $P_0$, $P_1$, , だけでロープを構成します。

この操作を繰り返し、点 $P_0$ だけが残るまでロープを引っ張って、すべて回収しなければなりません。

魍魎ズが何かする前に、できるだけ早くアラタを捕まえなくてはいけません。そこで、まずアラタを捕まえるロープの長さを最小にし、そのようなロープの中で、最後まで回収するために必要な力の合計を最小にします。この二つの値を最小にする修行部の皆さんの移動方法を見つけなければなりません。先生、手伝っていただけますか？

ウミカは必ず $1$ 行 $1$ 列にのみ存在し、アラタのいるマスはちょうど一つである。

アラタを捕まえられる入力のみが与えられる。

実行時間制限

2000 ms

メモリ制限

256 MB

チェッカー

CUSTOM