Practice on Toph

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

Srikant VS Terrorists

By Joyeeta.28 · Limits 1s, 512 MB

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 kk-th minute. There are nn cells (which are more like dungeons) numbered from 11 to nn 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 ii leads to cell aia_i. If he cannot remember any road for a cell, it will be denoted by 00. The time required to move from one cell to the other is exactly 11 minute.


The number of mm terrorists are guarding one or more cells. Srikant must kill all the terrorists within kk 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 kk-th minute, he cannot save JK because on that very minute the terrorist will shoot JK and kill him.

Srikant has rr rounds of bullets in his possession (each round consists of 66 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.]

Input

The first line contains five space-separated integers n,mn,m(1n,m106)(1 \le n,m \le 10^6), kk (1k109){(1 \le k \le 10^9)}, rr(1r109)(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 nn space-separated integers a1,a2,,ai,,ana_1,a_2, \dots, a_i, \dots, a_n (0ain)(0 \le a_i \le n) that describe the cell numbers Srikant can move to.

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

Output

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.

Samples

InputOutput
6 4 6 3
6 4 2 0 3 5
2 3
3 5
5 4
6 5
Yes
InputOutput
5 3 3 3
5 4 0 0 2
1 18
2 4
2 2
No

    Discussion

    Statistics


    80% Solution Ratio

    faria_efaEarliest, 2M ago

    prodip_bsmrstuFastest, 0.1s

    prodip_bsmrstuLightest, 12 MB

    antihashShortest, 824B

    Submit

    Login to submit

    Editorial

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

    Related Contests

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