【问题描述】

某电力公司需要修建一套电网对众多城镇进行供电。电网设施包括建造在城镇中的变电站，与建造在城镇间的输电线路。根据前期的考察结果，电力公司已经确定了哪些城镇之间需要建造输电线路，以使得所有城镇能够被连接成一个电力网络。每座城镇只需要建造一个变电站，却都向电力公司提供了多个建造候选地址。对于每个城镇，不同候选地址的变电站造价不同；对于城镇间的输电线路，其造价也会随着两端变电站的候选地址的变化而变化。因此，电力公司想要知道，在所有候选地址的组合中，电网的总造价（变电站造价加上输电线路造价）最低是多少。

【输入格式】

输入的第一行包括三个正整数 N、M、K。表示一共有 N 座城镇，需要建造 M 条输电线路，每座城镇都提供了 K 个变电站候选地址。

接下来输入 N 行，每行表示一个城镇。每行包含 K 个整数，表示该城镇不同候选地址的变电站造价。

接下来 M 行，每行表示一条输电线路，包含 K*K+2 个整数。前两个整数表示该输电线路两端的城镇，范围是 [0, N)。第三个整数开始是大小为 K×K 的矩阵 T 的行主序存储形式。Tij 表示当输电线路的第一个端点选择候选地址 i，第二个端点选择候选地址 j 时的线路造价。

【输出格式】

输出包含一行，这一行有一个整数，表示电网的最低总造价。

【样例输入】

2 1 2

1 2

3 4

0 1 1 2 3 4

【样例输出】

5

【样例说明】

城镇 0 与城镇 1 均选择了 0 号地址建造变电站。

【子任务】

对于全部数据，保证由城镇与输电线路构成的图是无向无重边无自环的连通图，保证单个变电站与单条线路的造价均不超过 1000。

对于 20% 的数据，保证 N≤6，K≤10。

对于另外 20% 的数据，保证 N≤10⁴，K≤10，M=N−1。

对于另外 20% 的数据，保证 N≤10⁴，K≤10，M=N。

对于另外 20% 的数据，保证 N≤10⁴，K≤10。图中存在两个节点 S、D，保证全图去除 D 节点和与 D 节点相连的边后，可以构成以 S 节点为根的一棵树，而且所有与 D 相连的节点都属于这棵树的叶子节点。

对于最后 20% 的数据，保证 N≤10⁴，K≤10，且度数大于 2 的节点数量 ≤6。