Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Srikant is an agent in an Intelligence agency. He is now heading a secret mission against a group of terrorists. His colleague, JK has been taken hostage by the terrorists. They are determined to kill JK on $k-$th minute. There are $n$ cells (which are more like dungeons) numbered from $1$ to $n$ in the territory of the terrorists.

Srikant had taken a road map of these cells with him while leaving for his mission but lost it before he reached there. He is standing at the first cell. He had tried to memorize the road map before he lost it. But his memory is not very sharp. He only remembers one road or none for each cell. The road he remembers for cell $i$ leads to cell $a_i$. If he cannot remember any road for a cell, it will be denoted by $0$. The time required to move from one cell to the other is exactly $1$ minute.

The number of $m$ terrorists are guarding one or more cells. Srikant must kill all the terrorists within $k$ minutes to save his colleague.

To move from a cell, Srikant needs to kill all the terrorists guarding the cell if there are any. Else he will get killed. Time after killing all the terrorists doesn’t count because JK will already be safe by then as nobody would be there to harm him. If Srikant reaches a cell to kill a terrorist on the $k-$th minute, he cannot save JK because on that very minute the terrorist will shoot JK and kill him.

Srikant has $r$ rounds of bullets in his possession (each round consists of $6$ bullets). Srikant must shoot each of the terrorists a number of times in order to break his shield, disarm him and finally kill him. This number may vary from one terrorist to the other. If the required bullets to kill a terrorist are greater than the number of bullets Srikant is left with, he cannot kill the terrorist and the terrorist shoots him back. For the convenience of calculation, the time required to kill a terrorist or to reload the gun is not taken into consideration.

YOUR TASK IS TO FIND OUT IF SRIKANT CAN SAVE JK.

[N.B: The number of times a terrorist needs to be shot is equivalent to the number of bullets needed to kill him.]

The first line contains five space-separated integers $n,m$$(1 \le n,m \le 10^6)$, $k$ ${(1 \le k \le 10^9)}$, $r$$(1 \le r \le 10^9)$ $-$ that denote the number of cells, total number of terrorists, the minute on which JK will be killed and the number of rounds of bullets.

The second line contains $n$ space-separated integers $a_1,a_2, \dots, a_i, \dots, a_n$ $(0 \le a_i \le n)$ that describe the cell numbers Srikant can move to.

Next $m$ lines contain two space-separated integers $x$ $(1 \le x \le n)$ and $y$ $(1\le y \le10^9)$ that denote the cell number the $j-$th ${(1 \le j \le m)}$ terrorist guards and the number of times he needs to be shot.

Print “Yes” if Srikant can save his colleague, otherwise print “No” (without quotes). You can print each letter in any case. For example, “YeS”, ”YES”, “yES”, “no”, ”NO” etc. are also acceptable.

Input | Output |
---|---|

6 4 6 3 6 4 2 0 3 5 2 3 3 5 5 4 6 5 | Yes |

Input | Output |
---|---|

5 3 3 3 5 4 0 0 2 1 18 2 4 2 2 | No |

80% Solution Ratio

faria_efaEarliest,

prodip_bsmrstuFastest, 0.1s

prodip_bsmrstuLightest, 12 MB

antihashShortest, 824B

Login to submit

The agent must kill all the terrorists before kkk minutes. And to kill all the terrorists, the total...

Toph uses cookies. By continuing you agree to our Cookie Policy.