돼지 잡기

시간 제한1초메모리 제한256 MB

요약
매일 방문하는 손님이 열쇠로 연 우리들 사이에서 돼지를 자유롭게 재분배할 수 있을 때, 손님이 원하는 한도 내에서 팔 수 있는 돼지의 총합을 최대화하는 문제입니다.
난이도

어려움10점 중 8점

유형
유니온 파인드, 그래프, 그리디
정답자
아직 제출이 없습니다

문제

종혁이는 자물쇠로 잠긴 M개의 돼지우리에서 일한다. 각 우리에는 처음에 정해진 수의 돼지가 들어 있지만, 종혁이는 열쇠가 없어 혼자서는 우리를 열 수 없다.

손님은 하루에 한 명씩 농장을 방문한다. 각 손님은 몇몇 우리의 열쇠를 가지고 있으며, 자신이 가진 열쇠로 열 수 있는 모든 우리를 연 뒤 원하는 수만큼 돼지를 사려고 한다.

하루의 진행은 다음과 같다.

  1. 손님이 도착하면, 그 손님이 가진 열쇠로 열 수 있는 모든 우리를 연다.
  2. 종혁이는 그 손님에게 돼지를 판다. 손님이 원하는 수를 초과해서 팔 수는 없지만, 그보다 적게 팔 수는 있다.
  3. 판매가 끝난 뒤, 종혁이는 아직 열려 있는 우리들 사이에서 남은 돼지를 원하는 대로 다시 배치할 수 있다.

각 우리에 들어갈 수 있는 돼지 수에는 제한이 없다. 모든 손님이 차례대로 방문할 때, 종혁이가 팔 수 있는 돼지 수의 최댓값을 구하라.

입력

첫째 줄에 돼지우리의 수 M(1 <= M <= 1,000)과 손님의 수 N(1 <= N <= 100)이 공백으로 구분되어 주어진다. 돼지우리는 1번부터 M번까지, 손님은 방문 순서대로 1번부터 N번까지 번호가 붙어 있다.

둘째 줄에는 각 돼지우리에 처음 들어 있는 돼지 수를 나타내는 M개의 정수가 공백으로 구분되어 주어진다. 각 값은 0 이상 1,000 이하이다.

다음 N개의 줄에는 손님 정보가 방문 순서대로 주어진다. i번째 손님을 나타내는 줄은 A K_1 K_2 ... K_A B 형식이다. 이는 그 손님이 K_1, K_2, ..., K_A번 우리의 열쇠를 가지고 있으며, 돼지 B마리를 사고 싶다는 뜻이다. A와 B는 0 이상의 정수이다. A가 0이면 열쇠 번호 없이 바로 B가 주어진다.

출력

첫째 줄에 팔 수 있는 돼지 수의 최댓값을 출력한다.

예제3

  1. 예제 1

    입력
    3 3
3 1 10
2 1 2 2 
2 1 3 3
1 2 6
    예상 출력
    7

  2. 예제 2

    입력
    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

  3. 예제 3

    입력
    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