配点 : $300$ 点

問題文

二次元平面の点 $(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$ 回の移動を行えるか判定してください。

制約

• $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$ 以外の入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $H$ $K$

$S$

$x_1$ $y_1$

$\vdots$

$x_M$ $y_M$

出力

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

4 2 3 1
RUDL
-1 -1
1 0

Yes

初め高橋君の体力は $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$ になってもいいことに注意してください。

5 2 1 5
LDRLD
0 0
-1 -1

No

初め高橋君の体力は $1$ です。以下で移動を説明します。

• $1$ 回目の移動： $S_i$ が L なので点 $(-1,0)$ に移動する。高橋君の体力は $0$ に減る。
• $2$ 回目の移動： $S_i$ が D なので点 $(-1,-1)$ に移動する。高橋君の体力は $-1$ に減る。体力が $-1$ になってしまったので、高橋君は倒れてしまい、移動をやめる。

以上より、高橋君は倒れてしまうので、No を出力してください。

高橋君がはじめいる点 $(0,0)$ にはアイテムが置いてありますが、移動後にアイテムは消費されるので、$1$ 回目の移動前にアイテムを消費しないことに注意してください。