AT_abc303_c [ABC303C] Dash

现在高桥在一个二维平面上。初始时他在 $(0,0)$ 处，生命值为 $H$。平面上有 $M$ 个可以恢复生命值的物品，其中第 $i$ 个物品的位置为 $(x_i,y_i)$。 高桥将要进行 $N$ 次移动，第 $i$ 次移动的方式如下： - 设高桥现在的位置是 $(x,y)$，那么他将会消耗 $1$ 点生命值，同时： - 如果 $S_i=\texttt R$，移动到 $(x+1,y)$； - 如果 $S_i=\texttt L$，移动到 $(x-1,y)$； - 如果 $S_i=\texttt U$，移动到 $(x,y+1)$； - 如果 $S_i=\texttt D$，移动到 $(x,y-1)$。 - 如果高桥的生命值降为负数，他就会倒下无法行动；否则，如果当前位置有一个可以恢复生命值的物品，且当前生命值小于 $K$，那么生命值将会恢复到 $K$。 请判断高桥能否进行完所有的移动而不倒下。 #### 数据范围与约定 $1\le N,M,H,K\le2\times10^5$，$|x_i|,|y_i|\le2\times10^5$。 保证 $S$ 是一个只由字符 `R`、`L`、`U`、`D` 构成的长度为 $N$ 的字符串。保证 $(x_i,y_i)$ 两两不同。保证所有输入的数均为整数。

第一行输入四个数 $N,M,H,K$。第二行输入一个长度为 $N$ 的字符串 $S$。接下来 $M$ 行，第 $i$ 行输入两个数 $(x_i,y_i)$。

如果高桥可以进行完所有 $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 $ 回目の移動前にアイテムを消費しないことに注意してください。