| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 10 | 10 | 8 | 100.000% |
Albert는 "보안 게임" 이라는 보드 게임을 즐겨한다. 이 게임은 총 $N$ 개의 보안용 로봇을 적절히 활용하여 $M$ 개의 건물을 보호하는 것이 목표인데, 몇 가지 까다로운 규칙이 있다.
편의상 $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]$ 이라 하자.
다른 예로, $N = 4, M = 3,ドル $g = [3, 1, 1, 1],ドル $x = [[1, 2, 3], [1], [1], [3]]$ 그리고 $L = [1, 2, 1],ドル $U = [2, 2, 2]$ 이라 하자.
입력으로 $N, M, g, x, L, U$가 주어졌을 때, $B$ 값에 따라 Albert가 얻을 수 있는 최대 점수를 구해보자 (즉, $S_1, S_2, \dots, S_B$).
입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, M$ 이 공백으로 구분되어 주어진다. 다음 $N$ 줄에 걸쳐 각 줄에는 $i$ 번째 로봇이 배치될 수 있는 건물의 수 $g_i$ 와 함께 건물의 번호인 $g_i$ 개의 정수가 ($x_{i,1}, x_{i, 2}, \dots, x_{i, g_i}$) 공백으로 구분되어 주어진다 (즉, 각 줄에는 $g_i+1$ 개의 정수가 주어진다). 다음 $M$ 줄에 걸쳐 각 줄에 한 쌍의 정수 $L_k, U_k$ 가 주어지는데 이는 $k$ 번째 건물에 배치되어야 하는 최소/최대 로봇의 수를 나타낸다.
각 테스트 케이스의 정답인 $S_1, S_2, \dots, S_M$ 을 공백으로 구분하여 각 줄에 출력한다.
3 3 3 2 1 2 2 1 3 2 2 3 1 3 1 3 1 3 4 3 3 1 2 3 1 1 1 1 1 3 1 2 2 2 1 2 5 3 2 1 2 1 3 2 1 2 1 2 1 3 1 2 2 2 1 1
3 6 6 -1 -1 -1 4 5 5
예제 1: 본문에서 다루었다.
예제 2: 본문에서 다루었다.
예제 3: