Witch at Home

問題文

問題名の元ネタ： AtCoder Beginner Contest 176 D - Wizard in Maze

Teto ちゃんの家の庭の木々の間に有刺鉄線が張られています。
この庭の地図を $2W \times 2W$ のマス目で表し、左から $i$ 列目で、上から $j$ 番目のマスを マス $(i,j)$ と表します。
いくつかのマスの中にはそれぞれ $1$ 本の木が生えています。マスの境界には木はありません。
互いに辺で隣り合うマスに生えている $2$ 本の木は有刺鉄線でつながれている可能性があり、その $2$ 本の木の間を通る経路は危険です。

今、彼女はマス $(W,W)$ の右下角の点におり、庭の外まで移動しようとしています。
移動する前に、次のような魔法を何度でも使えます。

• 魔法：上下 $h$ マス、左右 $w$ マスからなる $h \times w$ の範囲を選び、その中に生えている木をすべて消します。
  ただし、範囲の縦横を入れ替えることはできず、範囲の境界はマスの境界と一致しなければなりません。

この魔法によって $2$ 本の木が隣り合わなくなった場所は、ワイヤーも取り除かれ、危険ではなくなります。

$W,h,w$ の値と、各マスに木が生えているかの情報が与えられます。
危険な経路を通らずに庭の外まで移動するとき、魔法を使う回数の最小値を求めてください。
経路の太さはないものとします。

入力

入力は以下の形式で与えられます。

$S_i$ $(1 \le i \le 2W)$ は長さ $2W$ の文字列です。 $S_i$ の $j$ 文字目を $c_{i,j}$ と表します。
$c_{i,j}$ $(1 \le i,j \le 2W)$ は、マス $(i,j)$ に木が生えているなら # 、生えていなければ . です。
$c_{i,j}$ $(1 \le i \le 2W,1 \le j \le 2W-1)$ と $c_{i,j+1}$ の間には空白はありません。

他に入力は以下の制約を満たします。

• $W,h,w$ は整数
• $1 \le W \le 500$
• $1 \le h \le 2W$
• $1 \le w \le 2W$

出力

魔法を使う回数の最小値を出力してください。
最後に改行してください。

サンプル

入力例1

3 6 6
.#####
#.##.#
##..##
#.#..#
##.###
####..

出力例1

0

マス目の左斜め上に向かって進む経路は危険ではありません。

入力例2

5 2 1
#.########
##########
#.########
##.######.
#########.
#########.
#########.
#..#######
#..#######
##########

出力例2

3

魔法を使う範囲の縦横を入れ替えることはできません。

入力例3

9 18 18
.....#............
.#####.###########
.#...#.#.........#
.#.#.#.#.#######.#
.#.#.#.#.#.....#.#
.#.#.#.#.#.###.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#####.#.#.#
.#.#.#.......#.#.#
.#.#.#########.#.#
.#.#...........#.#
.#.#############.#
.#...............#
.#################
..................

出力例3

1