Bessie có ~N~ chất hóa học được đánh số từ ~1~ đến ~N~ ~(N \leq 100)~, mỗi chất có a_i ~(0 \leq a_i\leq 10^4)~ đơn vị thể tích. Bessie biết ~K~ công thức kết hợp một đơn vị thể tích của một số chất để tạo thành một đơn vị thể tích của chất có chỉ số lớn hơn chỉ số của tất cả các chất thành phần. Biết rằng mỗi chất Bessie chỉ biết nhiều nhất một công thức tạo thành.

Hãy cho biết thể tích lớn nhất của chất thứ ~N~ sau khi Bessie thực hiện biến đổi các chất dựa trên các công thức đã biết.

Input

• Dòng đầu chứa số ~N~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~

• Dòng thứ ba chứa số nguyên ~K~

• Mỗi dòng trong ~K~ dòng tiếp theo bắt đầu với hai số nguyên ~L~ và ~M~ ~(M>=1)~, theo sau là ~M~ số nguyên cho biết M chất thành phần để tạo thành một đơn vị thể tích chất thứ ~L~.

Output

Một số nguyên là thể tích lớn nhất của chất thứ ~N~ sau khi Bessie thực hiện biến đổi các chất dựa trên các công thức đã biết.

Ví dụ

Input

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

Output

1