Perfect Word Transformation

Patrik has redefined the notion of a perfect word. Given a word of length \(N\) and \(Q\) subwords specified by intervals \([L_i, R_i]\) for \(1 \le i \le Q\), the uncovered substring of a subword is formed by the letters in the subword that have not been covered by snow. Initially, no letter is covered by snow.

Krešimir throws \(K\) snowballs, each covering a letter at a given position (if not already covered). After each snowball, the corresponding letter becomes covered and is ignored in the subwords. The word is called a perfect word if all \(Q\) uncovered substrings, corresponding to the \(Q\) subwords, are pairwise distinct.

Determine the minimum number of snowball throws after which the word becomes perfect. If the word never becomes perfect, output \(-1\).

inputFormat

The first line contains three integers \(N\), \(Q\), and \(K\).

The second line contains a string of length \(N\).

The next \(Q\) lines each contain two integers \(L\) and \(R\) (with \(1 \le L \le R \le N\)), representing a subword.

The last line contains \(K\) integers, representing the positions (1-indexed) of the letters that Krešimir covers, in order.

outputFormat

Output a single integer: the minimum number of snowball throws required for the word to become perfect, or \(-1\) if it never becomes perfect.

sample

5 2 3
abcde
1 3
3 5
2 4 1

0