Luôn muốn tìm hiểu những thứ mới, cô bò Bessie đang học cách biến đổi kim loại. Cô ấy có \(a_i(0 \leq a_i \leq 10^4)\) miếng kim loại \(i\) \((1\leq i\leq N\leq100)\). Hơn nữa, cô ấy biết \(K(1\leq K\leq N)\) công thức để kết hợp một miếng của một số kim loại để tạo thành một miếng kim loại có chỉ số cao hơn tất cả các kim loại cấu thành. Ngoài ra, với mỗi kim loại, Bessie biết nhiều nhất một công thức chế tạo nó.

Tính số miếng kim loại \(N\) nhiều nhất Bessie có thể có được sau những phép biến đổi.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_i\).
• Dòng thứ ba chứa số \(K\).
• \(K\) dòng tiếp theo bắt đầu bằng hai số nguyên \(L,M\) \((1\leq M)\), theo sau là \(M\) số nguyên. \(M\) số nguyên cuối cùng biểu thị các kim loại được dùng để tạo thành miếng kim loại \(L\). Dữ liệu đảm bảo rằng \(L\) lớn hơn \(M\) số nguyên cuối cùng.

Output

In ra số miếng kim loại \(N\) nhiều nhất Bessie có thể có sau khi áp dụng các phép biến đổi hoặc không làm gì.

Scoring

• Subtask \(1\): Một miếng kim loại \(i\) có thể biến thành miếng kim loại \(i+1\).
• Subtask \(2\): Mỗi công thức biến một miếng kim loại này thành một miếng kim loại khác.
• Subtask \(3\): Không có điều kiện gì thêm.

Example

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

1