409909: GYM103831 H Shopping

Grisha, a young coder, goes shopping for groceries every Saturday. This time he has decided to minimize his spending.

Grisha's town has N grocery shops, and for convenience he has numbered them from 1 to N. Some shops are connected with minibus routes, and the cost of the minibus from the ith shop to the jth one is p_ij rubles.

There are K different kinds of groceries. The shops stock limited amount of each. Grisha also knows the price for each kind of groceries in each shop. The prices in the shops may differ.

Grisha lives near the shop number 1, so he spends nothing to get there. He may finish his shopping in any of the N shops. Assume that the return home will also cost him nothing.

Given a shopping list, determine the minimum necessary amount of money that Grisha will have to take with him.

The first line of the input contains a single integer N (1 ≤ N ≤ 17), the number of shops.

The following N lines form an N × N matrix P. The matrix elements p_ij (0 ≤ p_ij ≤ 2000) determines the cost of minibus from the ith shop to the jth shop. If p_ij = 0, it means that there is no direct minibus route connecting the shops number i and j. The matrix is symmetric, and all p_ii are zero.

The next line holds a single integer number K (1 ≤ K ≤ 50), the number of types of groceries.

The next line holds K integers Q_i (1 ≤ Q_i ≤ 2000), the required amount of each grocery type on Grisha's shopping list.

What follows is K blocks describing the grocery stocks and prices in the shops. The ith block starts with a line holding a single integer M, the number of shops that have the ith grocery type. Each of the M following lines of the block holds three integers v, p, q (1 ≤ v ≤ n, 0 ≤ p ≤ 2000, 1 ≤ q ≤ 2000) meaning that the shop number v sells the ith grocery type for p rubles per piece and it has q pieces of that grocery.

A single number, the minimum sum of money that will allow Grisha to buy all the groceries. If that is impossible, output  - 1.

Solutions that fail the test in the example will be awarded 0 points and not be further tested.

Each test is scored separately.

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