问题描述

在二维平面上，高桥初始位于点 $(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$ 是一个长度为 $N$ 的字符串，由 R、L、U 和 D 组成。
• $|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。

示例输入 1

4 2 3 1
RUDL
-1 -1
1 0

示例输出 1

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$。

示例输入 2

5 2 1 5
LDRLD
0 0
-1 -1

示例输出 2

No

初始时，高桥的生命值为 $1$。我们描述各个移动如下：

• 第 $1$ 步移动：$S_i$ 是 L，所以他移动到点 $(-1,0)$。他的生命值减少为 $0$。

• 第 $2$ 步移动：$S_i$ 是 D，所以他移动到点 $(-1,-1)$。他的生命值减少为 $-1$。现在生命值为 $-1$，他虚脱并停止移动。

因此，他将会晕倒，所以应该输出 No。

注意虽然初始点 $(0,0)$ 上有一个物品，但在第 $1$ 步移动之前，他没有消耗它，因为物品只有在移动之后才会被消耗。