“请乘坐普朗特穿梭航空公司TB1024次航班前往纽约的旅客前往38号登机口乘坐摆渡车登机。”

小航作为普朗特的常旅客会员，在飞行的旅途中最喜欢研究的就是航空公司的航线图。通过研究航线图，小航可以从世界的某一处出发，乘坐许多不同次航班到达世界另外一个地方。他不由得感慨世界之大之美妙。

这一次旅途，小航在蝈蝈大会上从普朗特先生那里获得了一份普朗特穿梭航空的所有航线图。

普朗特穿梭航空的航班都是单向的，一趟航班连接了A、B两座城市，也就是说，一趟航班只能从A出发飞到B。除此之外，为了"Make (Prumpt Shuffle) Airlines Great Again (MAGA)"，普朗特先生特别将一趟航班的价格设为出发地和到达地落地价格的和。他认为这样是为了人民的飞行从此不同。

小航作为普朗特穿梭航空的常旅客会员，获得了一张环球旅行卡。即从全球任一城市出发，乘坐  趟普朗特穿梭航空的航班，满足

(1) 任意两趟挑出的航班都没有相同的起点 且

(2) 任意两趟挑出的航班都没有相同的终点。

同时因为普朗特先生的小气作风，他要求小航要挑出的航班的价格之和要最小。

由于小航还着急着统计票数，于是这个求出最小价格和的任务就交给你了。

注意,题目仅仅要求了任意两趟航班满足没有相同的起点或终点,没有其余的要求例如:终点跟下一趟的起点需要连续

输入描述:

第一行共有三个整数, , ，分别表示小航要选出  趟航班，可到达的城市数量 ， 以及可供选择的航班的数量 。城市的编号为  到 。
接下来  行共有  个整数 ，表示降落在第  个城市的价格。
每组数据的第    行至  行，描述一趟航班的起点和终点。

 的范围较大，因此输入文件较大，请使用较快的输入输出方式。
在这里给出一份快速读入模板：
namespace ae86 {
const int bufl = 1<< 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
    if (s == t) {
        t = (s = buf) + fread(buf, 1, bufl, stdin);
        if (s == t) return EOF;
    }
    return *s++;
}
inline int read() {
        int a = 0, b = 1, c = fetch();
        while(!isdigit(c)) b ^= c == '-', c = fetch();
        while(isdigit(c)) a = a * 10+ c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

输出描述:

输出文件共 1 行，为最小价格和。若无法选出符合要求的  条路径，则输出 NONE

4 6 9
3
5
4
6
10
2
4 3
5 4
6 3
5 6
6 5
1 2
1 4
2 4
3 2

36

备注:

对于所有的数据，保证 
对于的数据，满足
对于的数据，满足