تحب Bessie الهوايات الجديدة وتتعلم تحويل المعادن. لديها $a_i$ وحدات ($0 \le a_i \le 10^4$) من المعدن $i$ لكل $1 \le i \le N \le 100$. تعرف $K$ وصفات ($1\le K<N$) تجمع وحدة من كل معدن من عدة معادن في وحدة معدن رقمه أكبر من كل المكونات. تعرف على الأكثر وصفة تصنيع واحدة لكل معدن.

احسب أكبر عدد وحدات من المعدن $N$ بعد سلسلة تحويلات.

الإدخال

السطر الأول يحتوي $N$.

الثاني يحتوي $N$ أعداد صحيحة $a_i$.

الثالث يحتوي $K$.

الأسطر $K$ التالية تبدأ بعددين صحيحين $L$ و$M$ ($M\ge 1$)، ثم $M$ أعداد صحيحة للمكونات اللازمة لوحدة $L$. مضمون أن $L$ أكبر منها كلها.

الإخراج

أخرج أكبر عدد وحدات المعدن $N$ بعد صفر أو أكثر من التحويلات.

أمثلة

الإدخال 1

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

الإخراج 1

1

ملاحظة

سلسلة مثلى لهذا المثال:

1. تحويل وحدة معدن 1 إلى 2.
2. تحويل وحدة معدن 2 إلى 3.
3. تحويل وحدة من كل من 3 و4 إلى 5.

تبقى وحدة من المعدن 1 ووحدة من 5، ولا يمكن تصنيع مزيد من 5.

المهام الفرعية

• الاختبار 2: لكل $1 \le i < N$ يمكن تحويل وحدة $i$ إلى وحدة $i+1$.
• الاختباران 3 و4: كل وصفة تحول وحدة معدن إلى معدن آخر.
• الاختبارات 5–11: لا قيود إضافية.

نسبة المسألة: Nick Wu