题目来自第 30 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

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

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

2 1 2
1 2
3 4
0 1 1 2 3 4

5

样例 1 解释

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

子任务

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

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。