Maximum Chain Length from Dominated Substrings

Consider a string $S$. Tiffany extracts $n_a$ substrings of $S$, denoted as $A_i = S(la_i, ra_i)$ for $1\le i \le n_a$. Similarly, Yazid extracts $n_b$ substrings from $S$, denoted as $B_i = S(lb_i, rb_i)$ for $1 \le i \le n_b$. Additionally, there are $m$ dominance relations. Each relation is given in the form $(x, y)$ and means that the $x$-th $A$ string dominates the $y$-th $B$ string.

We call a string $T$ a valid target string if there exists a segmentation: [ T = t_1 + t_2 + \cdots + t_k \quad (k \ge 0), ] where each segment $t_i$ exactly equals one of the $A$ strings (i.e. $t_i = A_{id_i}$ for some valid index) and for every pair of consecutive segments $t_i$ and $t_{i+1}$ (for $1 \le i < k$) there exists a $B$ string dominated by $A_{id_i}$ that is a prefix of $A_{id_{i+1}}$.

Let $|A_i|$ denote the length of the substring $A_i$ (i.e. $ra_i - la_i + 1$). The goal is to compute the maximum possible total length (i.e. $\sum_{i=1}^{k}|A_{id_i}|$) of a valid target string $T$. If there exist valid chains of arbitrarily large length, output (-1).

The relation between substrings is defined with the notation:

• $A_i = S(la_i, ra_i)$ is the substring of $S$ between indices $la_i$ and $ra_i$, inclusive.
• $B_i = S(lb_i, rb_i)$ is defined similarly.
• A relation $(x, y)$ means that $A_x$ dominates $B_y$.
• The condition that $B_y$ is a prefix of $A_j$ means that the string corresponding to $B_y$ exactly matches the starting characters of $A_j$.

Your task is to compute and output a single integer representing the maximum length of the target string $T$ as described above, or (-1) if the length can be made arbitrarily large.

inputFormat

The input is given as follows:

1. A line containing the string $S$.
2. A line containing three integers $n_a$, $n_b$, and $m$, denoting the number of $A$ strings, $B$ strings, and the number of dominance relations, respectively.
3. $n_a$ lines follow, each containing two integers $la_i$ and $ra_i$ describing the $i$-th $A$ string as the substring of $S$ from index $la_i$ to $ra_i$ (1-indexed).
4. $n_b$ lines follow, each containing two integers $lb_i$ and $rb_i$ describing the $i$-th $B$ string.
5. $m$ lines follow, each containing two integers $x$ and $y$, representing a dominance relation where $A_x$ dominates $B_y$.

You can assume that indices are 1-indexed and that the substrings are valid segments within $S$.

outputFormat

Output a single integer: the maximum possible length of a valid target string $T$, or \(-1\) if the length can be made arbitrarily large.

sample

abcde
2 2 1
1 3
3 5
1 2
3 4
1 1

6