Бесі вивчає, як трансформуються метали. У неї є \(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\) цілих чисел. Ці \(M\) чисел представляють метали у способі комбінування металів, щоб отримати одну одиницю металу \(L\). Гарантується, що \(L\) більше ніж кожне із цих \(M\) чисел.

Формат вихідних даних

Виведіть максимальну кількість одиниць металу \(N\), які може отримати Бесі після серії із 0 або більше трансформацій.

Приклад вхідних даних

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

Приклад вихідних даних

1

У цьому прикладі оптимальна наступна серія трансформацій:

1. Трансформувати 1 одиницю металу 1 до металу 2.

2. Трансформувати 1 одиницю металу 2 до металу 3

3. Трансформувати 1 одиницю металу 3 та металу 4 метал 5.

   Тепер у Бесі одна одиниця металу 1 та 1 одиниця металу 5. Вона може отримати більше одиниць металу 5.

   ОЦІНЮВАННЯ:

   • У тесті 2 для \(1 \le i < N\), одна одиниця металу \(i\) може бути трансформована в одну одиницю металу \(i+1\).

   • У тестах 3 і 4 кожна трансформація перетворює одну одиницю одного металу в одну одиницю іншого металу.

   • У тестах 5 – 11 немає додаткових обмежень.