시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 96 45 34 53.125%

문제

종혁이는 자물쇠로 잠긴 M개의 돼지우리가 있는 농장에서 일하고 있다. 종혁이는 열쇠가 없기 때문에 우리들을 열지 못한다.

이 농장에 손님들은 하루에 한명씩 방문한다. 이들은 몇몇 우리 열쇠를 가지고 있고, 이 우리들을 연 다음 자신이 원하는 만큼의 돼지를 사간다.

농장 운영 방식은 아래와 같다.

  1. 손님이 도착해서 가지고 있는 열쇠로 열 수 있는 모든 우리들을 연다.
  2. 손님에게 몇몇 돼지들을 판다. (손님이 원하는 이상의 돼지를 팔 순 없지만 그 이하로는 팔 수 있다.)
  3. 종혁이는 팔고 남은 돼지들을 현재 열려져 있는 우리들을 상대로 재분배 할 수 있다.

문제는 우리에 들어갈 수 있는 돼지 숫자의 제한이 없다고 할 때 손님들이 방문한 동안 종혁이가 최대로 팔 수 있는 총 돼지의 숫자를 구하는 것이다.

입력

첫째 줄에 돼지 우리 숫자를 나타내는 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

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Final Exam #1 2번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: HJY