1004. toys

题目描述

小 H 是一家幼儿园的园长，幼儿园里面有 $n$ 个小朋友。

小 H 想给小朋友买一件玩具。

玩具店一共有 $m$ 种玩具，每个小朋友会喜欢这 $m$ 种玩具的一部分。

由于物以稀为贵，当某种玩具的库存越来越少的时候，那么它的单价将会越来越贵。

具体的，如果第 $j$ 次购买第 $i$ 件玩具的话，将会花费 $w_{i, j}$ 的价格，保证 $w_{i, j} \ge w_{i,j-1}$。

小 H 想知道，在能够为所有小朋友买到一件心仪的玩具的情况下，怎么样才能花费最少。

输入格式

第一行一个整数 $T（1\le T\le 10）$，表示数据组数。

对于每组数据，第一行输入两个整数 $n, m（1\le n,m\le 1000）$，表示小朋友个数以及玩具个数。

接下来 $n$ 行，第 $i$ 行会先输入一个正整数 $x_i$，表示第 $i$ 个小朋友喜欢的玩具个数；接下来会输入 $x_i$ 个不同的正整数，表示第 $i$ 个小朋友喜欢的玩具编号。保证每组数据中，$\sum x_i \le 10^4$。

接下来 $m$ 行，每行先输入一个整数 $y_i$，保证 $y_i$ 等于这个玩具被多少个学生喜欢；接下来会输入 $y_i$ 个正整数，其中第 $j$ 个表示 $w_{i, j}（1\le w_{i, j}\le 10^9）$

输出格式

对于每组数据，输出所需要花费的最小值。

样例输入

1
3 2
1 1
2 1 2
1 2
2 3 100
2 50 200

样例输出

153

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1004