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.

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

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

***For Sample #1:*** 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$. ***For Sample #2:*** 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.

AtCoder [ABC303C]