问题

在AtCoder国，有许多城镇存在。 为了管理城镇，存在市，市是城镇的集合。 市内的城镇通过道路相连。通过这些道路，可以往返于市内的所有城镇。 但是，仅凭这些道路无法移动到其他市中的城镇。 因此，在AtCoder国，为了解决这个问题，通过在多个市中管理一些城镇来连接市与市，使得可以往返于所有的市。

由于在多个市中管理一个城镇非常麻烦，所以尽可能地减少共享的数量。 具体而言，假设有N个市，用k个市共享的城镇数为Sk，则满足Σ(Sk×(k-1))=N-1。

高桥君是AtCoder国的交通大臣，他希望将修建道路的成本总和尽可能地减小。 但是他对只有一个计划表示不安，所以决定考虑第k个最好的计划。

该计划的内容如下：

• 无论穿越哪两个城镇，移动时都不会重复经过同一个城镇，使得路径仅确定为一个。
• 修建道路指的是减少城镇之间的道路。

他发现满足这个条件的计划有很多。 因此，将计划的成本定义为修建道路的总成本。 成本越小，计划越好。

请输出第k个最好的计划的成本。如果第k个值不存在，则输出-1。

输入

输入是通过标准输入给出的。已附加约束的描述。 第一行包含三个整数A、T和k。 接下来的2×A行给出了与各个市相关的城镇信息。

• 前N（2≦N≦7）行表示属于第i个市的城镇数。
• Ci,j（1≦Ci,j≦T）表示属于第i个市的第j个城镇。

M表示道路的数量，是一个非负整数。从输入的最后一行开始的M行给出了道路的信息。

• Cityi,1和Cityi,2表示第i条道路连接的城镇。也就是说，Cityi,1和Cityi,2可以双向移动，属于同一个市。
• Costi（1≦Costi≦77）表示第i条道路的修建成本。

输出

请输出第k个最好的计划的成本。如果第k个值不存在，则输出-1。

示例

输入示例1：

3 7 1
3
1 2 3
3
3 4 5
3
5 6 7
9
1 2 1
1 3 2
2 3 3
3 4 3
3 5 6
4 5 9
5 6 9
5 7 18
6 7 27

图：输入示例1的示意图

输出示例1：

13

图：输出示例1的示意图

• 第1个最好的计划是删除连接城镇1和城镇2的道路，删除连接城镇3和城镇4的道路，删除连接城镇5和城镇6的道路。

输入示例2：

2 3 2
2
1 2
2
2 3
2
1 2 1
2 3 1

输出示例2：

-1

• 第2个最好的计划的成本不存在，因此输出-1。

输入示例3：

4 9 2
3
1 2 3
3
3 4 5
3
5 6 7
3
5 8 9
12
1 2 1
1 3 1
2 3 1
3 4 3
3 5 3
4 5 3
5 6 6
5 7 3
6 7 9
5 8 9
5 9 18
8 9 27

输出示例3：

16

• 成本为16的计划是最小的，但是有9种可以达到相同成本的计划。因此，第2个计划的成本也是16。

来源

ARC 009