AT_mujin_pc_2018_e 迷路

[problemUrl]: https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e $ N $ 行 $ M $ 列のマス目があります。上から $ i $ 行目、左から $ j $ 列目にあるマスを $ (i,j) $ で表します。 特に、左上のマスは $ (1,1) $ であり、右下のマスは $ (N,M) $ です。 マス目の状態は 二次元配列 $ s $ で表され、$ s_{ij} $ が `#` のときマス $ (i,j) $ には障害物があり、`.` または `S` または `G` のとき障害物はありません。 ロボットは $ 0 $ 秒に`S` のマスから スタートし、 `G` のマスに出来るだけ短い時間で辿り着こうとします。 しかしロボットは常にどの方向にも動けるというわけではありません。 長さ $ K $ の文字列 $ d $ が与えられます。毎秒、ロボットは隣接するマスに移動するか、今いるマスにとどまることができます。ただし、$ t $ 秒後から $ t+1 $ 秒後にかけては、$ t $ を $ K $ で割った余りを $ r $ ($ 0\ \leq\ r\ \leq\ K-1 $) として、 $ d_{r+1} $ の方向にのみ $ 1 $ 秒かけて $ 1 $ マス進むことが出来ます。現在いるマスを $ (i,j) $ とした時、$ d_{r+1} $ が `U` の場合は $ (i-1,j) $ に、 `D` の場合は $ (i+1,j) $ に、`L` の場合は $ (i,j-1) $ に、 `R` の場合は $ (i,j+1) $ に移動できます。マス目の外に出るような移動や、障害物があるマスへの移動は出来ません。 この条件のもとで `S` から`G` のマスに辿り着くまでの最短の時間を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ d_{1}...d_{K} $ $ s_{11}...s_{1M} $ $ : $ $ s_{N1}...s_{NM} $

ロボットが `S` から `G` まで移動するのにかかる最短の時間を出力せよ。ただし、どのように移動しても `S` から `G` まで移動出来ない場合は $ -1 $ を出力せよ。

### 制約 - $ 2\ \leq\ N,M\ \leq\ 1000 $ - $ 1\ \leq\ K\ \leq\ 100000 $ - $ s $ は `#` または `.` または `S` または `G` からなる - `S` と `G` の書かれたマスはそれぞれ $ 1 $ つずつ存在する - $ d $ の長さは $ K $ - $ d $ は `U` または `D` または `L` または `R` からなる - $ N,M,K $ は整数である ### Sample Explanation 2 どのように移動しても $ 2 $ 列目に移動出来ません。