← 返回题目列表

AtCoder · abc303_c

E. 冲刺

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

在二维平面上,高桥最初位于点 (0, 0),他的初始健康状况是 H. M 恢复生命值的物品被放置在飞机上;的 i- 其中第一个位于 (x_i,y_i).

高桥将使 N 移动。 的 i第一步移动如下。

  1. 让 (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.
  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

输出

打印 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 移动,因为物品仅在移动后消耗。