Migrated from Lutece 1355 柱爷与三叉戟不得不说的故事

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在喵哈哈城,人人都知晓柱爷有一把传奇武器三叉戟.据传,这是一位在$772002$年前陨落的强大守护者F91曾经使用过的12级灵能武器,拥有毁天灭地的力量

但只有很少人知道当柱爷获得三叉戟时，三叉戟的力量已经消失殆尽.为了能修复三叉戟的力量,柱爷苦心专研古籍,发现只有找到最神秘的$15$种元素,将元素的力量重新注入到三叉戟中,三叉戟就能恢复到原来的力量,于是柱爷踏上了寻找神秘元素的旅行.

柱爷首先发现$15$个由卿学姐掌控的地牢,里面正好有$15$种对应元素.冷静的柱爷没有贸然行动,经过一番详细的打听,柱爷得知了第$i$种元素需要$D{_i}$的精力去获得;与此同时,柱爷还发现了由白学潘看守的$N$个洞穴,第$i$个洞穴中有$A{_i}$
个不同的元素,分别是$B{_1},B{_2},...,B{_A{_i}}$,需要$C{_i}$的精力去获得.

同种元素不得拥有多个,不然元素之间会产生强大的斥力,会发生爆炸;不能攻下一个洞穴后,留有元素不拿走,元素可能会辐射,伤害喵哈哈村的大爷......

但是柱爷岂是凡人？柱爷修复三叉戟时花费的总是最小的精力！

那么这个最小的花费是多少呢？

Input

第一行包括$15$个正整数,第$i$个数表示$D{_i}$.

第二行包括一个整数表示$N$.

接下来$N$行,每行有一个整数表示$A_i$,后面紧接着$A_i$个不同的正整数,最后又一个正整数$C_i$表示需要花费的精力.

数据保证：

• $0 \leq N \leq 10000$

• $1 \leq D_i \leq 20000$

• $0 \leq A_i \leq 5$

• $1 \leq C_i \leq 2000000$

Output

输出一个整数$ans$:

表示至少花$ans$的精力去修复三叉戟.

Samples

9599 11186 3513 3112 19106 1171 4254 4786 11880 19550 4793 17049 10779 11096 9713
5
4 10 1 8 11 1212645
3 14 9 15 1655560
3 7 3 14 1161262
5 13 5 9 2 11 710512
0 980331

141587

Resources

2016 UESTC Training for Dynamic Programming