P5583 "SWTR-1" Ethan and Sets

$\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.

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 one line. If there is no solution, output $-1$. Otherwise, output two integers $L,R$.

--- ### 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