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 自动生成**

无

无