[Apio2013]道路费用

时间限制:20s      空间限制:128MB

题目描述


输入格式

第一行包含三个由空格隔开的整数N,M和K。接下来的 M行描述最开始的M 条道路
。这M行中的第i行包含由空格隔开的整数ai,bi和c i,表示有一条在a i和b i之间,费用为c i的双向道路。接下
来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi,表示有一条连接城镇xi和yi新道路
。最后一行包含N个由空格隔开的整数,其中的第j个为pj,表示从城镇j 前往城镇 1的人数。输入也满足以下约束
条件。1 ≤ N ≤ 100000;1 ≤ K ≤ 20;1 ≤ M ≤ 300000;对每个i和j,1 ≤ ci, pj ≤ 10^6;


输出格式

你的程序必须输出恰好一个整数到标准输出,表示能获得的最大的收入。


样例输入

5  5 1
3  5 2
1  2 3
2  3 5
2  4 4
4  3 6
1  3
10 20 30 40 50 

样例输出

400

提示

在样例中, Mr. Greedy应该将新道路(1,3)的费用设置为 5分钱。在这个费用下,他可以选择道路(3,5),(1,2),
(2,4)和(1,3)来最小化总费用,这个费用为   14。从城镇 3出发的 30个人和从城镇 5出发的 50个人将经过新道
路前往城镇 1,因此他可以获得为(30+50)_5=400 分钱的最好收入。如果我们这样做,将新道路(1,3)的费用设置
为 10分钱。根据传统的限制,Mr. Greedy必须选择(3,5),(1,2),(2,4)和(2,3),因为这是唯一费用最小的集合
。因此,在嘉年华的过程中道路(1,3)将没有任何收入。


题目来源

没有写明来源