Ethan's Magical Collections

Ethan has n number collections. For each collection i (1 ≤ i ≤ n):

• Index: the i-th collection has index i.
• Size: the collection contains num_i numbers.
• Magic: the collection has magic value t_i.
• Numbers: the collection contains the numbers c_i,1, c_i,2, ..., c_i,numi.

In Ethan's world there are exactly m+1 numbers: 0, 1, 2, ..., m. Out of these, Ethan likes d numbers given by p₁, p₂, ..., p_d; the remaining numbers are the ones he dislikes.

Ethan wants to delete some collections by choosing a contiguous interval [L,R] (1 ≤ L ≤ R ≤ n) and keeping only the collections whose indices lie in that interval. His requirements are:

1. The remaining collections must collectively contain all the numbers he likes at least once.
2. Among all intervals satisfying the first requirement, he wants the total number of occurrences of his disliked numbers in the remaining collections to be as small as possible.
3. If there are multiple intervals with the same minimum count of disliked numbers, he chooses the one with the maximum total magic value (i.e. the sum of t_i for all collections in that interval).

Your task is to find an interval [L,R] that meets the criteria. If there is no such interval, output -1. If there are multiple answers, output any one of them.

Note: If a number appears multiple times in the remaining collections and it is a disliked number, each occurrence is counted separately.

Mathematical formulation:

Let F be the union multiset of numbers in collections L through R. Define:

\[ \text{DislikedCount}(L,R)=\sum_{x \in \{0,1,...,m\} \setminus \{p_1,\dots,p_d\}} \text{count}_F(x), \]

\[ \text{MagicSum}(L,R)=\sum_{i=L}^{R} t_i. \]

Find an interval [L,R] such that:

1. For every liked number p, \(\text{count}_F(p) \ge 1\).
2. \(\text{DislikedCount}(L,R)\) is minimized.
3. Among intervals minimizing \(\text{DislikedCount}(L,R)\), \(\text{MagicSum}(L,R)\) is maximized.

inputFormat

The first line contains three integers: n (number of collections), m (defines the range of numbers from 0 to m), and d (number of liked numbers).

The second line contains d distinct integers: p₁, p₂, ..., p_d (the liked numbers).

Then, for each collection i (1 ≤ i ≤ n), there are two lines:

• The first line contains two integers: num_i and t_i (the size of the collection and its magic value).
• The second line contains num_i integers: c_i,1, c_i,2, ..., c_i,numi (the numbers in the collection).

outputFormat

If a valid interval exists, output two integers L and R (1-indexed) separated by a space; otherwise, output -1.

sample

3 5 2
1 3
3 10
1 2 3
2 5
1 0
2 7
3 4

1 1