잭과 콩 자루

시간 제한3초메모리 제한512 MB

요약

각 농장이 가장 불리한 종류를 고르는 상황에서 필요한 콩 개수를 확보하기 위해 잭이 사야 하는 소의 최소 수를 구한다.

난이도: 어려움10점 중 8점
유형: 게임 이론, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

잭은 낯선 사람에게서 평범한 콩 한 자루를 받았다. 종류별로 필요한 만큼 콩을 모으면 거대한 콩나무를 키워서 그 끝에 있는 보물까지 올라갈 수 있다는 말도 함께 들었다.

모자란 콩은 마을의 다른 농장에서 얻어야 한다. 농장마다 기르는 콩 종류가 정해져 있다. 잭이 어느 농장에 콩을 달라고 하면 그 농장은 콩을 정확히 한 개 준다. 다만 잭은 값을 치르지 않으므로 어떤 종류를 줄지는 농장이 고른다. 그 농장이 기르는 종류 중 아무거나 줄 수 있고, 같은 농장이라도 방문할 때마다 다른 종류를 줄 수 있다. 잭은 어느 농장이든 원하는 만큼 여러 번 찾아갈 수 있다.

낯선 사람은 소도 받는다. 소 한 마리를 넘기면 잭이 말한 종류의 콩 한 개를 받는다.

잭은 실패할 가능성을 조금도 남기고 싶지 않다. 농장이 매번 잭에게 가장 불리한 종류를 고른다고 가정하자. 농장이 어떻게 고르더라도 모든 종류의 콩을 필요한 개수 이상 모으려면, 잭이 데려가야 하는 소는 최소 몇 마리인가?

입력

첫째 줄에 콩 종류의 수 $B$ ( $1 \le B \le 20$ )가 주어진다.
둘째 줄에 종류별로 필요한 콩의 개수 $V_1, \dots, V_B$ ( $0 \le V_i \le 100$ )가 주어진다.
셋째 줄에 마을에 있는 다른 농장의 수 $T$ ( $1 \le T \le 100$ )가 주어진다.
다음 $T$ 개의 줄에 농장 하나의 정보가 각각 주어진다. 각 줄은 그 농장이 기르는 콩 종류의 수 $M$ ( $1 \le M \le B$ )으로 시작하고, 이어서 서로 다른 정수 $M$ 개 $t_1, \dots, t_M$ ( $1 \le t_i \le B$ )이 주어진다. 이 정수는 그 농장이 기르는 콩 종류를 뜻한다.

출력

농장이 어떻게 고르더라도 콩나무를 키울 만큼 콩을 모으려면 잭이 데려가야 하는 소의 최소 마리 수를 한 줄에 출력한다.

예제3

예제 1
입력
```
1
5
1
1 1
```
예상 출력
```
0
```
예제 2
입력
```
3
5 5 5
2
2 1 2
2 2 3
```
예상 출력
```
10
```

예제 3

입력

10
6 0 5 0 0 0 0 8 0 7
4
3 1 3 8
3 1 3 10
3 8 10 3
3 10 8 1

예상 출력