游走配对
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一张n个点m条边的无向连通图，点权为a_i，一条路径的权值为它所经过点的点权和，给出q个x_i和q个y_i，每次你可以选择一对(x_i,y_j)（x_i，y_j都未被用过），然后从x_i走到y_j，代价为路径上的点权和，要求最小化走q次的代价；另外，一个点每被一条路径经过，它的点权都会增加b_i，即第k次经过i节点的权值为

输入描述:

第一行三个数n，m，q
接下来n行，每行两个数a_i,b_i，表示一个点的初始点权和每次增加的点权
接下来m行，每行两个数c_i,d_i，表示一条无向边
接下来一行q个数x_i
接下来一行q个数y_i

输出描述:

一个整数，表示走q次的最小代价
示例1

输入

复制 
4 4 2
1 2
3 4
5 6
7 8
1 2
2 3
3 4
4 1
1 2
3 4

输出

复制 
16

说明

选择(1,4),(2,3)两对，路径分别为1\to 4,2\to 3，代价为1 + 3 + 5 + 7 = 16

备注: