페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5112
서브태스크

연금술사(Alchemy) 2초 1024MB

문제

연금술을 취미로 공부하고 있는 홍윤이는 1 <= i <= N인 금속 i에 대하여 a_i개의 금속 조각을 갖고 있다. 

 

또한, K개의 특별 조합법을 알고 있는데, 각 특별 조합법을 사용하면 여러 개의 금속 조각들을 하나씩 이용하여 

소모한 재료들 모두보다 번호가 큰 금속 하나를 만들 수 있다. 

 

또한, 각 금속마다 그 금속을 만들기 위한 특별 조합법은 최대 하나임이 보장된다. 

 

이 때, 몇 번의 변환을 거쳐 홍윤이가 만들 수 있는 금속 N 조각의 최대 개수를 구해보자.


입력

다음과 같은 형식으로 입력이 주어진다.

N

a_1 \space a_2 \space ... \space a_N

K

L_1 \space M_1 \space P_{1,1} \space P_{1,2} \space ... \space P_{1,M1}

L_2 \space M_2 \space P_{2,1} \space P_{2,2} \space ... \space P_{2,M2}

...

L_k \space M_k \space P_{k,1} \space P_{k,2} \space ... \space P_{k,Mk}

 

N은 금속의 종류 수를 의미한다.

a_i는 i번째 금속의 초기 개수를 의미한다.​

그 다음 마지막 K개의 줄에는 특별 조합법의 완성 금속 L_i가 주어지고 재료 금속의 개수 M_i가 주어진다.

이후 M_i개의 재료 금속이 한 줄로 주어진다. L_i가 재료 금속들보다 번호가 큼이 보장된다.

이는 다른 말로 K개의 조합법은 M_i개의 금속 P_1 \sim P_{Mi}으로 L_i를 만들 수 있다는 의미다.

 

[제약 조건]

1 \le N \le 100

1 \le K \lt N

0 \le a_i \le 10,000


출력

첫 줄에 홍윤이가 만들 수 있는 금속 N 조각의 최대 개수를 출력하시오.


부분문제

번호 점수 조건
#115점

1 \le i \lt N인 모든 i에 대하여 금속 i하나를 금속 i+1하나로 바꿀 수 있는 특별 조합법이 존재한다.

#225점

모든 조합법은 한 금속을 다른 한 금속으로 전환한다.

#360점

추가 제한 조건 없음


예제1

입력
5

2 0 0 1 0

3

5 2 3 4

2 1 1

3 1 2
출력
1

출처

USACO 2022 US Open Bronze

역링크 공식 문제집만