시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 954 | 423 | 320 | 46.990% |
종혁이는 자물쇠로 잠긴 M개의 돼지우리가 있는 농장에서 일하고 있다. 종혁이는 열쇠가 없기 때문에 우리들을 열지 못한다.
이 농장에 손님들은 하루에 한 명씩 방문한다. 이들은 몇몇 우리 열쇠를 가지고 있고, 이 우리들을 연 다음 자신이 원하는 만큼의 돼지를 사간다.
농장 운영 방식은 아래와 같다.
문제는 우리에 들어갈 수 있는 돼지 숫자의 제한이 없다고 할 때 손님들이 방문한 동안 종혁이가 최대로 팔 수 있는 총 돼지의 숫자를 구하는 것이다.
첫째 줄에 돼지 우리 숫자를 나타내는 M(1≤M≤1,000)과 손님들의 숫자를 나타내는 N(1≤N≤100)이 공백으로 구분되어 주어진다. 돼지우리는 1번부터 M번까지의 숫자로 매겨져 있고 손님 역시 1번부터 N번의 숫자로 매겨져 있다.
두 번째 줄에는 각각의 돼지우리에 있는 초기 돼지 숫자를 나타내는 M개의 수가 공백으로 구분되어 주어진다. 이 수는 0 이상 1,000 이하의 수이다.
그 다음 N개의 줄에는 N명의 손님들에 대한 정보가 주어진다. i+2번째 줄에는 i번째 손님에 대한 정보 A, K1, K2, …, KA, B가 주어지는데 이는 i번째 손님이 K1, K2, …, KA번째 우리 열쇠를 가지고 있고 B마리의 돼지를 사길 원한다는 의미이다. A와 B는 0 이상의 정수이다.
첫째 줄에 최대 팔 수 있는 돼지 숫자를 출력한다.
3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6
7
6 6 6 3 2 0 1 3 2 1 2 0 1 3 3 1 1 1 2 2 3 8 2 4 5 2 2 4 6 6
15
11 5 1 2 2 1 0 2 4 1 1 1 2 5 1 2 3 4 5 3 4 1 2 6 7 5 2 3 8 1 3 3 6 11 5 3 8 9 10 3
17