H. Магазины
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
shops.in
вывод
shops.out

Молодой программист Гриша каждую субботу ходит за продуктами. В этот раз он решил минимизировать свои расходы.

В городе, где проживает Гриша, имеется N продовольственных магазинов. Для удобства он пронумеровал магазины от 1 до N. Между некоторыми магазинами ходят маршрутные такси. Стоимость проезда с i-го магазина в j-й составляет pij рублей. Всего продается K разных типов продуктов. В магазинах имеется определенное количество единиц того или иного продукта. Также Гриша знает, сколько стоит каждый продукт в каждом из магазинов. Цены на продукты в различных магазинах могут быть разными.

Гриша живет рядом с магазином с номером 1. Для того, чтобы добраться до этого магазина, он ничего не платит. Конечным магазином может быть любой из N магазинов. На обратную дорогу домой Гриша ничего не тратит.

Имея список покупок, определите наименьшую сумму денег, которую Гриша должен взять с собой.

Входные данные

В первой строке находится единственное целое число N (1 ≤ N ≤ 17) — количество магазинов.

Следующие N строк содержат матрицу N × N. Элемент матрицы pij (0 ≤ pij ≤ 2000) указывает стоимость проезда с i-го магазина в j-й. Если pij равно 0, то это значит, что нет прямого маршрута с i-го магазина в j-й. Матрица симметрична. Элементы на главной диагонали всегда равны нулю.

В следующей строке находится единственное целое число K (1 ≤ K ≤ 50) — количество различных продуктов.

Далее идут K целых чисел Qi (1 ≤ Qi ≤ 2000) — количество единиц каждого вида продукта, которое нужно купить.

Затем идут K блоков, которые указывают, в каких магазинах продаются товары, и по какой стоимости. Каждый i-й блок начинается со строки, где находится единственное целое M — количество магазинов, где продается i-й продукт. Далее в M строках имеется по три целых числа v p q (1 ≤ v ≤ n, 0 ≤ p ≤ 2000, 1 ≤ q ≤ 2000) — в магазине с номером v продается i-й продукт по цене p за штуку, и в этом магазине имеется q товаров этого типа.

Выходные данные

В единственной строке выведите наименьшую сумму денег, которую Гриша должен взять с собой. Если нет возможности купить все товары, то надо вывести одно число  - 1.

Система оценки

Представленное на проверку решение сначала проходит тестирование на тесте из примера, приведенного в условии задачи. Если на этом тесте решение участника выдает правильный ответ, то тогда это решение проверяется с использованием комплекта тестов для этой задачи (при этом баллы за каждый тест начисляются независимо). В противном случае решение участника считается неверным, и за него участнику не начисляются какие-либо баллы.

Пример
Входные данные
5
0 1 3 0 2
1 0 5 0 5
3 5 0 7 2
0 0 7 0 2
2 5 2 2 0
3
3 5 5
3
1 3 2
3 2 1
5 4 3
3
2 4 3
3 5 4
5 2 1
4
1 9 1
2 8 2
3 7 3
4 6 1
Выходные данные
70