当前没有测试数据。

C - Dash

得分：300 分

问题描述

在二维平面上，高橋初始位于点 $(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。

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$ 步移动之前没有消耗它，因为物品只能在移动之后消耗。