冲刺

题目描述

在二维平面上,高桥最初位于点 $(0, 0)$,初始体力为 $H$。平面上放置了 $M$ 个可以恢复体力的道具,其中第 $i$ 个道具位于 $(x_i,y_i)$。

高桥将进行 $N$ 次移动。第 $i$ 次移动如下。

设 $(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)$。

如果高桥的体力变为负数,他会倒下并停止移动。否则,如果移动到的地方放置了道具,且他的体力严格小于 $K$,那么他会使用该道具将体力恢复为 $K$。

判断高桥能否不倒下地完成 $N$ 次移动。

输入格式

输入按以下格式从标准输入给出:

N M H K
S
x_1 y_1
⋮
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$ 次移动前他不会使用它,因为道具只在移动后才被使用。

数据范围

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