AT_abc303_c [ABC303C] Dash

[problemUrl]: https://atcoder.jp/contests/abc303/tasks/abc303_c 二次元平面の点 $ (0,0) $ に高橋君がいます。初め、高橋君の体力は $ H $ です。また、二次元平面には $ M $ 個の体力を回復するアイテムがあり、$ i $ 個目のアイテムは点 $ (x_i,y_i) $ に置いてあります。 高橋君は、これから $ N $ 回の移動をします。$ i $ 回目の移動は以下の方法で行われます。 1. 今高橋君がいる点を $ (x,y) $ とする。体力を $ 1 $ 消費し、$ S $ の $ i $ 番目の文字 $ S_i $ に応じて以下の点に移動する。 - $ S_i $ が `R` のとき： $ (x+1,y) $ - $ S_i $ が `L` のとき： $ (x-1,y) $ - $ S_i $ が `U` のとき： $ (x,y+1) $ - $ S_i $ が `D` のとき： $ (x,y-1) $ 2. 高橋君の体力が負になった場合、高橋君は倒れてしまい、移動をやめる。そうでない場合、移動した点にアイテムがあり、かつ高橋君の体力が $ K $ 未満ならば、移動した点に置かれたアイテムを消費し、高橋君の体力が $ K $ になる。 高橋君が一度も倒れることなく $ N $ 回の移動を行えるか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ H $ $ K $ $ S $ $ x_1 $ $ y_1 $ $ \vdots $ $ x_M $ $ y_M $

高橋君が一度も倒れることなく $ N $ 回の移動を行える場合 `Yes` を、そうでない場合 `No` を出力せよ。

### 制約 - $ 1\leq\ N,M,H,K\leq\ 2\times\ 10^5 $ - $ S $ は `R`, `L`, `U`, `D` からなる長さ $ N $ の文字列 - $ |x_i|,|y_i|\ \leq\ 2\times\ 10^5 $ - $ (x_i,y_i) $ は互いに異なる - $ S $ 以外の入力は全て整数 ### Sample Explanation 1 初め高橋君の体力は $ 3 $ です。以下で移動を説明します。 - $ 1 $ 回目の移動： $ S_i $ が `R` なので点 $ (1,0) $ に移動する。高橋君の体力は $ 2 $ に減る。点 $ (1,0) $ にはアイテムが置いてあるが、高橋君の体力は $ K=1 $ 以上なのでアイテムは消費されない。 - $ 2 $ 回目の移動： $ S_i $ が `U` なので点 $ (1,1) $ に移動する。高橋君の体力は $ 1 $ に減る。 - $ 3 $ 回目の移動： $ S_i $ が `D` なので点 $ (1,0) $ に移動する。高橋君の体力は $ 0 $ に減る。点 $ (1,0) $ にはアイテムが置いてあり、体力は $ K=1 $ 未満なのでアイテムを消費し、体力が $ 1 $ になる。 - $ 4 $ 回目の移動： $ S_i $ が `L` なので点 $ (0,0) $ に移動する。高橋君の体力は $ 0 $ に減る。 以上より、高橋君は倒れずに $ 4 $ 回の移動を行えるので、`Yes` を出力してください。体力は $ 0 $ になってもいいことに注意してください。 ### Sample Explanation 2 初め高橋君の体力は $ 1 $ です。以下で移動を説明します。 - $ 1 $ 回目の移動： $ S_i $ が `L` なので点 $ (-1,0) $ に移動する。高橋君の体力は $ 0 $ に減る。 - $ 2 $ 回目の移動： $ S_i $ が `D` なので点 $ (-1,-1) $ に移動する。高橋君の体力は $ -1 $ に減る。体力が $ -1 $ になってしまったので、高橋君は倒れてしまい、移動をやめる。 以上より、高橋君は倒れてしまうので、`No` を出力してください。 高橋君がはじめいる点 $ (0,0) $ にはアイテムが置いてありますが、移動後にアイテムは消費されるので、$ 1 $ 回目の移動前にアイテムを消費しないことに注意してください。