C - Dash Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 は R, L, U, D からなる長さ N の文字列
  • |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 を出力せよ。

入力例 1

4 2 3 1
RUDL
-1 -1
1 0

出力例 1

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 になってもいいことに注意してください。

入力例 2

5 2 1 5
LDRLD
0 0
-1 -1

出力例 2

No

初め高橋君の体力は 1 です。以下で移動を説明します。

  • 1 回目の移動： S_i が L なので点 (-1,0) に移動する。高橋君の体力は 0 に減る。

  • 2 回目の移動： S_i が D なので点 (-1,-1) に移動する。高橋君の体力は -1 に減る。体力が -1 になってしまったので、高橋君は倒れてしまい、移動をやめる。

以上より、高橋君は倒れてしまうので、No を出力してください。

高橋君がはじめいる点 (0,0) にはアイテムが置いてありますが、移動後にアイテムは消費されるので、1 回目の移動前にアイテムを消費しないことに注意してください。

Score : 300 points

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

  1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of 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. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

  • 1\leq N,M,H,K\leq 2\times 10^5
  • S is a string of length N consisting of R, L, U, and D.
  • |x_i|,|y_i| \leq 2\times 10^5
  • (x_i, y_i) are pairwise distinct.
  • All values in the input are integers, except for S.

Input

The input is given from Standard Input in the following format:

N M H K
S
x_1 y_1
\vdots
x_M y_M

Output

Print Yes if he can complete the N moves without being stunned; print No otherwise.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

  • 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

  • 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

  • 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

  • 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

  • 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

  • 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.