srg生存大冒险 - Problem

Description

在一个二维平面上，srg最初位于点 (0, 0) ，他的初始健康值是 $H$ 。在平面上放置了 $M$ 个可以恢复健康的物品，其中 $i$ 个放置在 $(x_i, y_i)$ 处（每个位置可放多个物品）。

srg将走 $N$ 步。第 $i$ 步棋如下。

假设 ($x$, $y$) 是他当前的坐标。根据 $S_i$ ，即 $S$ 的第 $i$ 个字符，他消耗 1 的健康值移动到下面一点：
- ($x+1$,$y$) 如果 $S_i$ 是 "R"；
- ($x-1$,$y$) 如果 $S_i$ 是 "L"；
- ($x$, $y+1$) 如果 $S_i$ 是 "U"；
- ($x$, $y-1$) 如果 $S_i$ 是 "D"。
如果 $srg$ 的健康值为负数，他就会倒下并停止移动。否则，如果在他移动到的位置放置了物品，且他的健康值严格小于 $K$ ，那么他就会消耗那里的一个物品，使他的健康值变为 $K$ 。

判断 $srg$ 是否可以在不被眩晕的情况下完成 $N$ 个动作。

Input

输入内容由标准输入法提供，格式如下:
N M H K （1≤N,M,H,K≤2×10⁵ )

$S$
$X_1$ $Y_1$
⋮⋮
$X_M$ $Y_M$

(∣x_i∣,∣y_i∣≤2×10⁵ )

Output

如果srg能完成 N 步而不被击晕，则打印 "Yes"；否则打印 "No"。

Sample Input Copy

4 2 3 1
RUDL
-1 -1
1 0

Sample Output Copy

Yes

HINT

```
Yes
```

最初，srg的健康状况是 $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$ （第3步） $S_i$ 是 "L"，所以他移动到了 $(0,0)$ 点。他的生命值降低到了 $0$ 。


因此，他可以下 $4$ 步棋而不会崩溃，所以应打印 "是"。请注意，健康值可能会达到 $0$ 。

Source/Category

admin