猫が空の容器に入ると液体のような性質を示すことはよく知られています。
数学者のペトロフは、自身の飼い猫を例にこの現象を観察し、さまざまな種類の容器を作って猫を入れる実験を繰り返しました。その結果、猫は常に自分の位置をできるだけ低く、より正確には、体の最高点の高さを最小にするように選ぶことがわかりました。容器内に複数の窪みがある場合、猫は入れる窪みの中で最も低いものを選びます。
ペトロフの頭に素晴らしい考えが浮かびました。実は、猫は量子最適化のいくつかの問題を解くためのアナログコンピュータとして使えるのではないかということです！この仮説を検証するため、数学者のペトロフは以下の数学モデルを考案しました。
容器を $n \times m$ のサイズの表 $T$ と見なします。いくつかのセルは壁であり、残りのセルは空です。以下の条件を満たすとき、容器への猫の配置は最適であると言います。
- 猫はいくつかの空のセルを占有します。猫が占有するすべてのセルは、$k$ 個のセルからなる連結した形状を形成します。形状が連結であるとは、その形状に含まれるどのセルからどのセルへも、隣接するセル（およびその間のすべてのセルも猫が占有している必要があります）を通って移動できることを指します。
- 猫が占有する最も高いセルの高さ $h$ が可能な限り低くなるようにします。表の行には $1$ から $n$ までの番号が付けられており、行番号が小さいほど高い位置にあるとします。
残念ながら、数学者のペトロフはプログラミングに詳しくありません。彼はあなたに、与えられた表 $T$ と猫の体積 $k$ に対して、猫が占有する最も高いセルの高さ $h$ を求めるよう依頼しました。
入力
1 行目には、整数 $n, m, k$ ($1 \le n, m \le 1000, 1 \le k \le 10^6$) が与えられます。
続く $n$ 行には、それぞれ $m$ 個の記号が含まれており、表 $T$ の説明を表しています。$i$ 行目の $j$ 番目の記号は、$T$ の $i$ 行目と $j$ 列目の交差するセルに対応します。「#」はそのセルが壁であることを意味し、「.」はそのセルが空であることを意味します。
出力
猫の最適な配置において、最も高い位置にあるセルが含まれる行番号を出力してください。猫を容器に配置できない場合は、「-1」を出力してください（引用符は含めません）。
入出力例
入出力例 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
4
入出力例 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
2
入出力例 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
2
注記
各サンプルにおける猫の最適な配置は以下のようになります。
