It's that time of year again where programmers solve copious numbers of competitive programming problems! Of course, Alice's favorite category of programming problems is Dynamic Programming, and she wants to solve as many Dynamic Programming problems as she can in a given amount of time.

Alice is in a contest where she has ~T~ minutes to solve ~N~ problems (all Dynamic Programming problems) numbered from ~1~ to ~N~. Using her magical future-predicting skills, she has predicted a number ~t_i~ for each problem which is how many seconds the problem will take to solve. Of course, being a very skilled programmer, she already knows how to solve the easier problems, so she will be satisfied if she just solves the ~N~th problem.

However, Mallory hates Dynamic Programming! Using her magical contest-tampering skills, she modifies the online judge such that some problems are locked behind other problems! That is, if problem ~3~ is locked behind problems ~1~, ~2~, and ~4~, at least one of problems ~1, 2, 4~ have to be solved before problem ~3~ is available. If a problem isn't locked behind anything, then there's no way to solve "at least one" dependency, so the problem becomes unsolvable! Gosh darn it, Mallory!

Realizing this, Alice uses her magical anti-contest-tampering skills to revert what Mallory has done. However, magic is tiring work, so she can only use magic to revert one problem; that is, she can make any one problem solvable without the need to solve one of its dependencies.

Alice wants to know the number of unique problems ~1 \leq i \leq N~ she can choose to apply magic to such that she can finish solving problem ~N~ within ~T~ minutes.

Constraints

~1 \leq N \leq 2 \cdot 10^5~

~1 \leq M \leq \min(\frac{N(N-1)}2, 10^6)~

~1 \leq T, t_i \leq 10^7~

For 30% of the problem points, ~1 \leq N \leq 50~.

Input specification

The first line will contain two space-separated integers ~T~ and ~N~. The second line will contain ~N~ space-separated integers ~t_i~ for ~1 \leq i \leq N~, the number of seconds problem ~i~ will take to solve. The third line will contain one integer ~M~, the number of dependency relations there are. The next ~M~ lines will contain two space-separated integers ~a, b~, which means that solving problem ~a~ will allow problem ~b~ to be solved.

Output specification

The first and only line of output will contain one integer, the number of problems Alice can choose to "unlock" so that she can solve problem ~N~ within ~T~ minutes.

Sample Input 1

1 5
1 10 5 15 40
3
2 4
3 4
4 5

Sample Output 1

3

Sample Explanation 1

Alice can unlock problems ~3~, ~4~, or ~5~:

• If she unlocks ~3~, she can solve problems ~3, 4, 5~ in ~5 + 15 + 40 = 60~ seconds.
• If she unlocks ~4~, she can solve problems ~4, 5~ in ~15 + 40 = 55~ seconds.
• If she unlocks ~5~, she can solve it in ~40~ seconds.

However:

• If she unlocks ~1~, there's no way to solve problem ~5~.
• If she unlocks ~2~, The fastest (and only) way to solve problem ~5~ is to solve problems ~2, 4, 5~ in ~10 + 15 + 40 = 65~ seconds, which is over the time limit of 1 minute.

Sample Input 2

1 5
5 4 3 60 1
6
5 4
4 3
3 5
1 2
2 1
3 3

Sample Output 2

2