보안 게임

Albert는 "보안 게임"이라는 보드 게임을 즐겨 한다. 이 게임의 목표는 $N$개의 보안용 로봇을 적절히 활용하여 $M$개의 건물을 보호하는 것이다. 게임에는 다음과 같은 규칙이 있다.

1. 각 로봇은 최대 $B$개의 서로 다른 건물을 동시에 보호할 수 있다.
2. 모든 로봇이 모든 건물을 보호할 수 있는 것은 아니다. $i$번째 로봇은 $g_i$개의 서로 다른 건물을 보호할 수 있으며, 이 건물들을 $x_{i,j}$로 나타낸다 ($1 \le j \le g_i$, $1 \le x_{i,j} \le M$).
3. $k$번째 건물은 최소 $L_k$대, 최대 $U_k$대의 서로 다른 로봇이 보호해야 한다. 각 건물의 점수는 그 건물을 지키는 로봇의 수로 정한다.
4. 위 규칙을 모두 지키면서 로봇을 배치했다면, 게임의 점수는 각 건물 점수의 총합이다. 위 규칙을 모두 지키면서 로봇을 배치할 방법이 없다면 게임의 점수는 -1점이다.

편의상 $S_b$는 $B = b$일 때 Albert가 얻을 수 있는 최대 게임 점수로 정의한다 ($1 \le B \le M$).

예를 들어 $N = M = 3$, $g = [2, 2, 2]$, $x = [[1, 2], [1, 3], [2, 3]]$, $L = [1, 1, 1]$, $U = [3, 3, 3]$이라 하자.

• $B = 1$이라면 로봇 1이 건물 2를, 로봇 2가 건물 1을, 로봇 3이 건물 3을 보호하는 방법으로 최대 3점을 얻을 수 있다. 이때 각 건물의 점수는 1점이고 게임의 점수는 3이다.
• $B = 2$라면 로봇 1이 건물 1과 2를, 로봇 2가 건물 1과 3을, 로봇 3이 건물 2와 3을 보호하는 방법으로 최대 6점을 얻을 수 있다. 이때 각 건물의 점수는 2점이고 게임의 점수는 6이다.
• $B = 3$ 이상이라도 6점보다 많은 점수를 얻을 방법은 없다. 따라서 $S = [3, 6, 6]$이다.

다른 예로, $N = 4$, $M = 3$, $g = [3, 1, 1, 1]$, $x = [[1, 2, 3], [1], [1], [3]]$, $L = [1, 2, 1]$, $U = [2, 2, 2]$라 하자.

• 2번 건물은 $L_2 = U_2 = 2$이므로 반드시 2대의 서로 다른 로봇이 보호해야 한다.
• 그런데 2번 건물을 보호할 수 있는 로봇은 1번뿐이므로, $B$의 값과 관계없이 게임의 점수는 -1점이다.
• 이 경우 $S = [-1, -1, -1]$이다.

입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 다음 $N$개의 줄에는 각각 $i$번째 로봇을 배치할 수 있는 건물의 수 $g_i$와 건물 번호 $x_{i,1}, x_{i,2}, \dots, x_{i,g_i}$가 공백으로 구분되어 주어진다. 즉 각 줄에는 $g_i + 1$개의 정수가 주어진다. 다음 $M$개의 줄에는 각각 $k$번째 건물에 배치되어야 하는 최소 로봇 수 $L_k$와 최대 로봇 수 $U_k$가 한 쌍의 정수로 주어진다.

각 테스트 케이스의 정답 $S_1, S_2, \dots, S_M$을 공백으로 구분하여 각 줄에 출력한다.

• $1 \le T \le 10$
• $1 \le N, M \le 200$
• $\sum_{1 \le i \le N} g_i \le 5000$
• $1 \le i \le N$인 $i$에 대하여:
  • $1 \le g_i \le M$
  • $1 \le x_{i,1}, x_{i,2}, \dots, x_{i,g_i} \le M$
  • $x_{i,1}, x_{i,2}, \dots, x_{i,g_i}$에 중복된 값은 없다
• $1 \le k \le M$인 $k$에 대하여: $1 \le L_k \le U_k \le N$