Giả Kim Thuật

Bessie đang học giả kim thuật. Cô ấy bắt đầu với $a_i$ đơn vị kim loại $i$ ($1\le i\le N$). Cô ấy biết $K$ công thức, mỗi công thức cho phép kết hợp một đơn vị của mỗi kim loại thành phần để tạo ra một đơn vị kim loại có số hiệu lớn hơn tất cả các kim loại thành phần. Mỗi kim loại có tối đa một công thức để tạo ra nó.

Hãy tìm số đơn vị kim loại $N$ tối đa có thể đạt được sau bất kỳ số lần biến đổi nào.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($0\le a_i\le {10}^4$)
• Dòng 3: Số nguyên $K$
• $K$ dòng tiếp theo: Mỗi dòng chứa hai số $L$ và $M$, tiếp theo là $M$ số nguyên, là danh sách các kim loại thành phần để tạo ra kim loại $L$

Dữ liệu ra

Một số nguyên duy nhất: số đơn vị kim loại $N$ tối đa có thể có.

Ràng buộc

• $1\le N\le 100$
• $0\le a_i\le {10}^4$
• $1\le K<N$
• Mỗi kim loại có tối đa một công thức
• Mọi kim loại thành phần trong công thức tạo ra kim loại $L$ đều có số hiệu nhỏ hơn $L$

Ví dụ