题目描述

二次元平面の点 $(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 を出力せよ。

题目大意

现在高桥在一个二维平面上。初始时他在 $(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。

4 2 3 1
RUDL
-1 -1
1 0

Yes

5 2 1 5
LDRLD
0 0
-1 -1

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$ 回目の移動前にアイテムを消費しないことに注意してください。