Project Scheduling with Prerequisites

You are given n projects, each with a deadline and a duration. Additionally, certain projects have prerequisites. A project u is a prerequisite for project v if u must be completed before v can begin. Your task is to determine the maximum number of projects that can be completed before their deadlines when you follow an ordering that respects all prerequisite relations.

The projects should be scheduled in a sequence such that all prerequisites are met. For each project, if the sum of durations up to that project does not exceed its deadline, then the project is considered completed before its deadline; otherwise, it is simply executed but counted as late. If there is a cyclic dependency among the projects (i.e. the prerequisites do not form a valid ordering), then no projects can be scheduled properly, and the answer should be 0.

The problem can be mathematically described as follows:

Given a directed acyclic graph (DAG) over n nodes, where each node i has a deadline \(d_i\) and a duration \(t_i\), and a set of directed edges representing prerequisites, find an ordering \(\sigma\) of the nodes that is a topological sort of the graph. Then, let \(T_j = \sum_{i=1}^{j} t_{\sigma(i)}\). The goal is to maximize the number of indices \(j\) such that \(T_j \le d_{\sigma(j)}\).

Input/Output must be handled via standard input (stdin) and standard output (stdout).

inputFormat

The first line contains an integer n denoting the number of projects.

The next n lines each contain two integers, representing the deadline and duration for each project.

The following line contains an integer m denoting the number of prerequisite pairs.

The next m lines each contain two integers u and v meaning that project u is a prerequisite for project v (1-indexed).

It is guaranteed that 1 ≤ u, v ≤ n.

outputFormat

Output a single integer: the maximum number of projects that can be completed before their respective deadlines following an order that respects all the prerequisite relations. If a valid ordering is not possible (i.e. a cycle exists), output 0.

## sample

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

3