Page not loading? Try clicking here.
Placeholder

#8638

쉬운 연금술사 1s 256MB

Problems

연금술을 취미로 공부하고 있는 정올이는 1번 금속부터 N번 금속까지 각각 1 \le i \le N인 금속 i에 대하여 a_i개의 금속 조각을 갖고 있다. 

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

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

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

이 때, 정올이가 금속 N을 만들 수 있는지 알아보자.


Input

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

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를 만들 수 있다는 의미다.

 

[제약 조건]

  • 2 \le N \le 10

  • 1 \le K \lt N

  • 0 \le a_i \le 10

  • 1 \le M_i \lt 10


Output

정올이가 금속 N을 만들 수 있으면 YES, 아니면 NO를 출력한다.


Example #1

5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2
YES

초기엔 5번 금속 조각이 없기에, 5번 금속을 만들기 위해 3번과 4번 금속이 하나씩 필요하다.

4번 금속은 이미 있으니 바로 사용이 가능하고,

3번 금속은 없으니 2번 금속을 하나 추가로 필요로 한다.

2번 금속은 없으니 1번 금속 하나가 필요한데, 1번 금속은 2개가 있기에 만들 수 있다.

즉, 5번 금속을 만드는 것이 가능하다.


Example #2

5
0 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2
NO


You must sign in to write code.