题目描述

现在高桥在一个二维平面上。初始时他在 $(0,0)$ 处，生命值为 $H$。平面上有 $M$ 个可以恢复生命值的物品，其中第 $i$ 个物品的位置为 $(x_i,y_i)$。

高桥将要进行 $N$ 次移动，第 $i$ 次移动的方式如下：

• 设高桥现在的位置是 $(x,y)$，那么他将会消耗 $1$ 点生命值，同时：
  • 如果 $S_i=\texttt R$，移动到 $(x+1,y)$；
  • 如果 $S_i=\texttt L$，移动到 $(x-1,y)$；
  • 如果 $S_i=\texttt U$，移动到 $(x,y+1)$；
  • 如果 $S_i=\texttt D$，移动到 $(x,y-1)$。
• 如果高桥的生命值降为负数，他就会倒下无法行动；否则，如果当前位置有一个可以恢复生命值的物品，且当前生命值小于 $K$，那么生命值将会恢复到 $K$。

请判断高桥能否进行完所有的移动而不倒下。

输入格式

第一行输入四个数 $N,M,H,K$。第二行输入一个长度为 $N$ 的字符串 $S$。接下来 $M$ 行，第 $i$ 行输入两个数 $(x_i,y_i)$。

输出格式

如果高桥可以进行完所有 $N$ 次移动，输出 Yes，否则输出 No。

4 2 3 1
RUDL
-1 -1
1 0

Yes

5 2 1 5
LDRLD
0 0
-1 -1

No

数据范围与约定

$1\le N,M,H,K\le2\times10^5$，$|x_i|,|y_i|\le2\times10^5$。

保证 $S$ 是一个只由字符 R、L、U、D 构成的长度为 $N$ 的字符串。保证 $(x_i,y_i)$ 两两不同。保证所有输入的数均为整数。

样例 1 解释

最初，高桥的健康状况是 $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$ 。

因此输出 Yes

样例 2 解释

输出示例 2

最初，高桥的健康状况是 $1$ 。

• 第 $1$ 步： $S_i$ 是 "L"，因此他移动到 $(-1,0)$ 点。他的健康值减少到 $0$ 。
• 第 $2$ 步： $S_i$ 是 "D"，所以他移动到了 $(-1,-1)$ 点。他的健康值减少到 $-1$ 。现在健康值为 $-1$ ，他倒下并停止移动。

因此，输出 No。

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