AT_abc303_c [ABC303C] Dash

题目描述

现在高桥在一个二维平面上。初始时他在 $(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$。

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

数据范围与约定

$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)$ 两两不同。保证所有输入的数均为整数。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

4 2 3 1
RUDL
-1 -1
1 0

输出 #1

Yes

输入输出样例 #2

输入 #2

5 2 1 5
LDRLD
0 0
-1 -1

输出 #2

No