Score : $300$ points

问题描述

在一个二维平面上，Takahashi 初始位于点 $(0, 0)$，并且他的初始生命值为 $H$。在平面上放置了 $M$ 个恢复生命值的物品；其中第 $i$ 个物品位于坐标 $(x_i,y_i)$。

Takahashi 将进行 $N$ 次移动。第 $i$ 次移动如下：

1. 设 $(x,y)$ 为他当前的坐标。根据 $S$ 的第 $i$ 个字符 $S_i$，他会消耗 $1$ 点生命值以移动到以下位置：
   • 若 $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$ 次移动。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 08:31:24