돼지 잡기

종혁이는 자물쇠로 잠긴 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가 주어진다.

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