問題文
城市是城镇的集合,其存在是为了管理城镇。
城内各乡镇均有公路相连。这些道路可通往市内所有城镇。
但是,您无法仅使用这些道路前往其他城市的城镇。
因此,在AtCoder的国家,为了解决这个问题,一些城镇由多个城市管理,并且城市之间相互连接,使得所有城市之间的出行成为可能。
管理一个城镇和多个城市是非常麻烦的,因此共享位置的数量要尽可能少。
具体来说, 假设有 N 个城市, k 个城市共享的城镇数量为 S_k 它变成 Σ(S_k×(k-1))=N-1 。
高桥先生是AtCoder国家的国土交通大臣,他希望尽可能降低开发每条道路的总成本。
然而,维护计划 1 我担心, k 我决定想出最好的计划。
计划内容如下。
- 在任何城镇之间旅行时,路线应准确无误 我想维护它,以便建立 1 。
- 发展道路意味着减少城镇之间的道路数量。
因此,我们决定该计划的成本是开发每条道路的总成本。
成本值越低,计划越好。
k 打印第一个最佳计划的成本。 如果第k个值不存在,则 打印-1。
入力
A T k
N_1
C_{11} C_{12} C_{13} ... C_{1N_1}
:
:
N_A
C_{N1} C_{N2} C_{N3} ... C_{NN_A}
M
city_{11} city_{12} cost_1
:
:
cost_{M1} city_{M2} cost_M
- 输入是 有一行 2×A+M+2 。
- 1 行中城市数量 A(1≦A≦77) , 城镇数量 T(1≦T≦A×7) ,一个非负整数 k(1≦k≦7,777,777) 。
- 2 从行 2×A+1 至行 2×A 行提供有关属于该城市的城镇的信息。 表示属于第
- N_i(2≦N_i≦7) ... i 个城市的城镇数量。 属于第
- C_{ij}(1≦C_{ij}≦T) ... i 个城市 代表第 j 个城镇。
- M 表示道路数量,为非负整数。直到输入结束 M 行给出道路信息。
- city_{i1} 和 city_{i2} 是 i 代表由道路连接的城镇。换句话说, city_{i1} 和 city_{i2} 可双向移动,属于同一城市。
- cost_i(1≦cost_i≦77) 是 i 表示开发道路所需的成本。
出力
-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 个计划具有相同的成本。因此,第二个方案所需的成本也是16。