Description

$\mathrm{Ethan}$ has $n$ sets of numbers. Each set has the following properties:

ID: The ID of the $i$-th set is $i$.

Size: The size of the $i$-th set is $num_i$.

Magic power: The magic power of the $i$-th set is $t_i$.

Numbers: The $i$-th set contains numbers $c_{i,1},c_{i,2},\dots,c_{i,num_i}$.

In Ethan's world, there are only $m+1$ numbers in total: from $0$ to $m$.

$\mathrm{Ethan}$ has special feelings about numbers. Among these $m+1$ numbers, there are $d$ numbers that he likes, namely $p_1,p_2,\dots,p_d$. The remaining $m-d+1$ numbers are those he does not like.

Now $\mathrm{Ethan}$ wants to delete some sets. More precisely, he wants to choose an interval $[L,R]$ and delete all sets whose IDs are outside this interval.

• He wants the remaining sets to contain all the numbers he likes.

• Also, among the remaining sets, the total count of numbers he does not like should be as small as possible (note: this count means occurrences. For example, if $1$ is a number that $\mathrm{Ethan}$ does not like, and there are $3$ occurrences of $1$ in the remaining sets, then it counts as $3$ disliked numbers).

• If there are multiple intervals that satisfy the above, he wants the sum of magic power of the remaining sets to be as large as possible.

Find an interval $[L,R]$ that meets the requirements. If there is no solution, output $-1$. If there are multiple solutions, output any one.

Input Format

The first line contains three integers $n,m,d$.

The second line contains $d$ integers $p_1,p_2,\dots,p_d$.

Lines $3$ to $n+2$: each line starts with two integers $t_i,num_i$, followed by $num_i$ integers $c_{i,1},c_{i,2},\dots,c_{i,num_i}$.

Output Format

Output one line. If there is no solution, output $-1$. Otherwise, output two integers $L,R$.

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

2 4

2 3 2
1 2
4 1 1
4 2 1 3

-1

4 3 2
1 2
1 1 3
1 2 1 2
1 1 2
1 3 1 2 3

2 3

Hint

Sample Explanation:

In sample $1$, $\mathrm{Ethan}$ can choose $[2,4]$. Then the remaining sets contain all the numbers he likes, and there are only $2$ occurrences of numbers he does not like in these sets.

In sample $2$, there is no valid solution.

Constraints:

This problem uses subtasks.

Subtask 1: $1 \leq n,m \leq 100$, $20\%$.

Subtask 2: $1 \leq n,m \leq 500$, $30\%$.

Subtask 3: $1 \leq n \leq 3000, 1 \leq m \leq 1000, 1 \leq t_i \leq 10^9$, $50\%$.

Translated by ChatGPT 5