Thích học sở thích mới, bò Bessie học biến đổi kim loại. Có $a_i$ đơn vị ($0 \le a_i \le 10^4$) kim loại $i$ với $1 \le i \le N \le 100$. Biết $K$ công thức ($1\le K<N$) ghép một đơn vị mỗi loại trong vài kim loại thành một đơn vị loại có số lớn hơn mọi nguyên liệu. Mỗi loại có tối đa một công thức chế tạo đã biết.

Tính số đơn vị kim loại $N$ lớn nhất sau một chuỗi biến đổi.

Dữ liệu vào

Dòng đầu chứa $N$.

Dòng hai chứa $N$ số nguyên $a_i$.

Dòng ba chứa $K$.

$K$ dòng tiếp bắt đầu bằng số nguyên $L$, $M$ ($M\ge 1$), rồi $M$ số nguyên nguyên liệu cho một đơn vị $L$. Bảo đảm $L$ lớn hơn tất cả chúng.

Dữ liệu ra

In số đơn vị kim loại $N$ lớn nhất sau không hoặc nhiều phép biến đổi.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Chuỗi tối ưu trong ví dụ:

1. Đổi một đơn vị kim loại 1 thành 2.
2. Đổi một đơn vị kim loại 2 thành 3.
3. Đổi một đơn vị mỗi loại 3 và 4 thành 5.

Còn một đơn vị kim loại 1 và một đơn vị 5; không thể tạo thêm 5.

Nhiệm vụ con

• Kiểm thử 2: với $1 \le i < N$ một đơn vị $i$ có thể thành một đơn vị $i+1$.
• Kiểm thử 3, 4: mỗi công thức đổi một đơn vị một loại thành loại khác.
• Kiểm thử 5–11: không ràng buộc thêm.

Ghi công bài toán: Nick Wu