Dash

AtCoder

IDabc303_c

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

4 2 3 1
RUDL
-1 -1
1 0

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$.

Input #2

5 2 1 5
LDRLD
0 0
-1 -1

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.

API Response (JSON)

{
  "problem": {
    "name": "Dash",
    "description": {
      "content": "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)$. ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc303_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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)$.\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments