103032: [Atcoder]ABC303 C - Dash

Problem Statement

On a two-dimensional plane, Takahashi is initially at point $(0, 0)$, and his initial health is $H$. $M$ items to recover health are placed on the plane; the $i$-th of them is placed at $(x_i,y_i)$.

Takahashi will make $N$ moves. The $i$-th move is as follows.

1. Let $(x,y)$ be his current coordinates. He consumes a health of $1$ to move to the following point, depending on $S_i$, the $i$-th character of $S$:

   • $(x+1,y)$ if $S_i$ is R;
   • $(x-1,y)$ if $S_i$ is L;
   • $(x,y+1)$ if $S_i$ is U;
   • $(x,y-1)$ if $S_i$ is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than $K$, then he consumes the item there to make his health $K$.

Determine if Takahashi can complete the $N$ moves without being stunned.

Constraints

• $1\leq N,M,H,K\leq 2\times 10^5$
• $S$ is a string of length $N$ consisting of R, L, U, and D.
• $|x_i|,|y_i| \leq 2\times 10^5$
• $(x_i, y_i)$ are pairwise distinct.
• All values in the input are integers, except for $S$.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $H$ $K$
$S$
$x_1$ $y_1$
$\vdots$
$x_M$ $y_M$

Output

Print Yes if he can complete the $N$ moves without being stunned; print No otherwise.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is $3$. We describe the moves below.

• $1$-st move: $S_i$ is R, so he moves to point $(1,0)$. His health reduces to $2$. Although an item is placed at point $(1,0)$, he do not consume it because his health is no less than $K=1$.

• $2$-nd move: $S_i$ is U, so he moves to point $(1,1)$. His health reduces to $1$.

• $3$-rd move: $S_i$ is D, so he moves to point $(1,0)$. His health reduces to $0$. An item is placed at point $(1,0)$, and his health is less than $K=1$, so he consumes the item to make his health $1$.

• $4$-th move: $S_i$ is L, so he moves to point $(0,0)$. His health reduces to $0$.

Thus, he can make the $4$ moves without collapsing, so Yes should be printed. Note that the health may reach $0$.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is $1$. We describe the moves below.

• $1$-st move: $S_i$ is L, so he moves to point $(-1,0)$. His health reduces to $0$.

• $2$-nd move: $S_i$ is D, so he moves to point $(-1,-1)$. His health reduces to $-1$. Now that the health is $-1$, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point $(0,0)$, he does not consume it before the $1$-st move, because items are only consumed after a move.

问题描述

在二维平面上，Takahashi 初始位于点 $(0, 0)$，初始生命值为 $H$。平面上放置了 $M$ 个可以恢复生命的物品，第 $i$ 个物品位于 $(x_i,y_i)$。

Takahashi 将进行 $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. 如果 Takahashi 的生命值变为负数，他就会晕倒并停止移动。否则，如果他移动到的点上放置了物品，并且他的生命值严格小于 $K$，那么他就会消耗那里的物品，使他的生命值变为 $K$。

判断 Takahashi 是否可以在不晕倒的情况下完成 $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

最初，Takahashi 的生命值为 $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

最初，Takahashi 的生命值为 $1$。下面是移动的描述。

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

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

因此，他将会晕倒，所以应该打印 No。请注意，尽管初始点 $(0,0)$ 处有物品，但在进行 $1$ 次移动之前他不会消耗它，因为物品只在移动后消耗。