AT_arc009_4.[ARC009D] 覚醒ノ高橋君

在 AtCoder 国，有很多城镇。为了便于管理，这些城镇被划分为若干市。在每个市内部，城镇间通过公路相连，确保市内的所有城镇都能互相到达。然而，这些公路并不能连接不同的市。因此，为了让所有市之间都可以通达，AtCoder 国允许某些城镇被多个市共享管理。

由于多个市共同管理一个城镇会增加管理难度，因此，这类共享的城镇数量应该尽量减少。具体地说，如果有 $N$ 个市，各市共享的城镇数为 $S_k$，则满足关系 $\sum(S_k \times (k-1)) = N-1$。

高桥君是 AtCoder 国的国土交通大臣，他希望尽可能降低公路整备的总成本。但为了确保计划的可行性，他希望至少制定出前 $k$ 个最佳的整备计划。

整备计划的要求是：

• 无论从哪个城镇到另一个城镇的路线，都应当是唯一的，且不经过重复的城镇。
• "整备公路"意味减少城镇间的道路。

高桥君发现有多种计划可以满足这些条件。因此每一个计划的成本被定义为整备所有公路所花费的总费用。成本越小，计划就越好。

请计算出第 $k$ 好的计划的总成本。如果不存在这样的计划，则输出 -1。

输入格式

• 第一行包含三个整数：市的数量 $A (1 \le A \le 77)$、总城镇数 $T (1 \le T \le A \times 7)$ 和整数 $k (1 \le k \le 7,777,777)$。
• 接下来是 $2 \times A$ 行，每两个连续的行描述一个市的信息。
  • 第 $2i-1$ 行的整数 $N_i (2 \le N_i \le 7)$ 表示第 $i$ 个市拥有的城镇数量。
  • 第 $2i$ 行的 $N_i$ 个整数 $C_{ij} (1 \le C_{ij} \le T)$ 表示这些城镇的编号。
• 紧接着的是 $M$ 行，每行描述一条公路的信息。
  • 每行三个整数 $city_{i1}$、$city_{i2}$ 和 $cost_i (1 \le cost_i \le 77)$，表示连接城镇 $city_{i1}$ 和 $city_{i2}$ 的公路以及其整备费用。

输出格式

• 输出一个整数，表示第 $k$ 好的计划的总整备成本。如果不存在这样的计划，则输出 -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

示例输出

13

数据范围与提示

• 市数量 $A$ 在 1 到 77 之间。
• 城镇数量 $T$ 不超过 $A \times 7$。
• 整备计划的数量 $k$ 在 1 到 7,777,777 之间。
• 每个市的城镇数量 $N_i$ 至少为 2，且最多为 7。
• 每条公路的整备成本 $cost_i$ 为正数，且不超过 77。

本翻译由 AI 自动生成