1628. 干饭 (hard version)

正值华南师范大学双创周,节约主义者CJN决定请他的朋友们一起去酒店吃饭。CJN的朋友们也都是节约粮食的好同志,对于第i名朋友,他不会点超过a_{i}道菜。而由于酒店里每道菜的数量有限,对于第i道菜,酒店最多只能做出b_i道。同时,CJN的朋友很神奇,对于喜欢的菜,他们总能吃个精光。所以,为了响应光盘行动,他们只会点他们喜欢吃的菜(假设他们喜欢的菜的数量和能够点的菜的最大数量一致)。CJN是一个为朋友着想的人,他想在不浪费粮食的情况下,让朋友们尽可能吃饱,因此,他想知道他的朋友们最多能吃多少道菜。

输入

第一行,输入n,m,代表朋友和菜的数量

2 - n + 1行,先输入一个整数a_i,代表第i个朋友最多能点的菜数,接下来,输入a_i个数字,对于第j个数字,代表第i个朋友喜欢第j道菜。

n + 2行,输入m个数字,代表对于第i道菜,酒店最多能做的数量b_i

输出

输出一个整数,代表朋友们最多能吃的菜数的总和。

样例

标准输入 复制文本
1 1
1 1
2
标准输出 复制文本
1
标准输入 复制文本
3 3
1 1
2 1 2
3 1 2 3
1 2 3
标准输出 复制文本
6

提示

数据保证n <= 1000, m <= 10000, a_i <= 10
样例2解释:对于第一个人,点一次第一道菜,对于第二个人,点两次第二道菜,对于第三个人,点三次第三道菜

来源

黄一肯

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 28
通过 5