高等术学
题号:NC25671
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

亵渎是炉石传说中术士的一张强力清场卡牌,常常可以消灭所有的随从。  

游戏中共有 n 个随从,编号为 1 到 n,第 i 个随从有 h[i] 的生命值,当随从生命值小于等于 0 时,随从死亡。第 i 个随从死亡后,会有 k[i] 个随从被召唤到场上,他们的编号为 c[i][j], j = 1, 2, 3, ..., k[i]。初始场上只有 1 号随从,保证整个过程中每个随从一定会出现且只会在场上出现一次。  

亵渎的效果如下:每次释放亵渎花费 1 的代价,释放亵渎的时候,对场上所有随从造成一定伤害,伤害为 d[1], d[2], ..., d[m], d[1], d[2], ... 如此循环,若该次释放有随从被消灭,则下一次释放花费代价为 0。  

求消灭所有随从的总花费。

输入描述:

第一行给出两个正整数 n, m,分别表示总随从数,伤害序列长度。

第二行给出 n 个正整数 h[1], h[2], ..., h[n],表示随从的生命值。

第三行给出 m 个正整数 d[1], d[2], ..., d[m],表示伤害序列。

接下来 n 行分别给出 1 到 n 号随从死亡后召唤随从的情况,

每行第一个数 k[i] 表示第 i 个随从死亡后,会有 k[i] 个随从被召唤到场上,接下来 k[i] 个数表示被召唤到场上的随从的编号。

保证 1 <= n<= 10^5, 1 <= m <= 10^5, 1 <= h[i] <= 10^9, 1 <= d[i] <=10^9, 所有 k[i] 之和不超过 10^5。

输出描述:

输出一个整数,表示总花费。
示例1

输入

复制
7 3
1 5 1 18 1 5 5
1 5 1
3 2 3 7
1 6
2 4 5
0
0
0
0

输出

复制
7