分数: 300 点
问题陈述
在二维平面上,高桥最初位于点 (0, 0),他的初始健康状况是 H. M 恢复生命值的物品被放置在飞机上;的 i- 其中第一个位于 (x_i,y_i).
高桥将使 N 移动。 的 i第一步移动如下。
-
让 (x,y) 是他当前的坐标。 他消耗了健康 1 移动到以下点,具体取决于 S_i, i- 第一个字符 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.
- (x+1,y) if S_i is
-
如果高桥的生命值变为负数,他就会倒下并停止移动。 否则,如果一个物品被放置在他移动到的位置,并且他的生命值严格小于 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
输出
打印 Yes 如果他能完成 N 移动时不被眩晕;打印 No 否则。
样本输入 1
4 2 3 1 RUDL -1 -1 1 0
示例输出 1
Yes
最初,高桥的健康状况是 3。 我们在下面描述这些动作。
-
1-st 动作: S_i is
R,所以他移动到指向 (1,0)。 他的健康状况下降至 2。 尽管物品被放置在点 (1,0),他不消耗它,因为他的生命值不低于 K=1. -
2-第二步: S_i is
U,所以他移动到指向 (1,1)。 他的健康状况下降至 1. -
3-rd 动作: S_i is
D,所以他移动到指向 (1,0)。 他的健康状况下降至 0。 物品被放置在点处 (1,0),并且他的健康状况低于 K=1,所以他消耗了该物品来恢复他的生命值 1. -
4第一步: S_i is
L,所以他移动到指向 (0,0)。 他的健康状况下降至 0.
因此,他可以使 4 移动时不会崩溃,所以
应打印 Yes 。 请注意,健康状况可能会达到 0.
示例输入 2
5 2 1 5 LDRLD 0 0 -1 -1
示例输出 2
No
最初,高桥的健康状况是 1。 我们在下面描述这些动作。
-
1-st 动作: S_i is
L,所以他移动到指向 (-1,0)。 他的健康状况下降至 0. -
2-第二步: S_i is
D,所以他移动到指向 (-1,-1)。 他的健康状况下降至 -1。 现在既然健康了 -1,他倒下并停止移动。
这样,他就会愣住,所以 No 。
请注意,虽然在他的初始点有一个项目 (0,0),他在之前没有消耗它 1-st 移动,因为物品仅在移动后消耗。