Time Limit: 6s Memory Limit: 256MB

题目描述

作为快乐小学的校长,现在你准备选出若干个小朋友排成一个队列,组织一次快乐的郊游。
你的学校里一共有 n 个班级,每个班至少有 1 个人。由于名额紧张,你只能从每个班级里选出 1 个人参加春游,每个班参加春游的那 1 个人在队列中的位置就是它所在的班级编号。即:1 班被选中的人就排在队列的第 1 个位置,2 班被选中的人就排在队列的第 2 个位置。
每一个小朋友有一个难受值 \(a_i\),为了让春游尽可能快乐,你需要使你选出的小朋友的难受值总和尽可能地低。
同时,还要考虑小朋友之间的人际关系:
有些小朋友之间的关系可能很好,如果它们被同时选中并且在队伍中位置相邻,那么会导致队伍的难受值降低;
有些小朋友之间的关系可能很差,如果它们被同时选中并且在队伍中位置相邻,那么会导致队伍的难受值升高;

确定一种组织郊游队列的方案使得队列的难受值尽可能低。

在你的学校里,学号以一种非常简单的方式给出:假设 1 班有 30 个人,2 班有 20 个人,3 班有 25 个人,那么 1 班的学生学号就是 1 到 30,2 班的学生学号就是 31 到 50,3 班的学生学号就是 51 到 75。

输入格式

第一行是一个正整数 \(T\;(1<=T<=100)\)
对于每一组数据,第一行包括一个整数 \(n \;(1<=n<=1000)\),表示班级个数。
接下来包括 n 行,依次描述 1 到 n 班的信息。
每一行首先是一个整数 \(k\;(1<=k<=40)\),表示该班级的学生个数,然后 K 个正整数 \(a_1, a_2, a_3, .. a_k\;(-1000 <= a_i <= 1000)\) 表示将这个班的学生按学号由低到高排序后,每个学生的难受值。
接下来包括一个整数 m \((0 <= m <= 100000\),表示学生之间的人际关系个数。
接下来包括 m 行,每行描述一个人际关系。
每一行包括三个整数 \(x, y, z\;(-1000<=z<=1000)\),表示学号为 \(x\) 的小朋友如果和学号为 \(y\) 的小朋友同时选出且位置相邻,那么队伍的难受值就会加上\(z\) 。

保证不会有重复的人际关系。
保证所有数据的班级数总和不超过 6000。

输出格式

对于每组数据,输出一行,包含一个数,表示可以组成的队列的最低难受值。

样例输入

1
2
3 10 20 30
3 40 50 60
1
1 4 1000

样例输出

60

样例解释

选出学号为 1 的小朋友和学号为 4 的小朋友的难受值总和是最低的,为 50,但是由于它们关系不好,如果把它们同时选出,恰好它们在队伍中的位置又相邻,那么队伍的总体难受值就会增加 1000 变成 1050;因此选出学号为 1 的小朋友和学号为 5 的小朋友才是最优的。(也可以选学号为 2 的小朋友和学号为 4 的小朋友)