题目描述：

有$n$座城市、$m$条道路（不排除重边或者自环），经过这条道路要缴纳相应的现金或者旅游金，现在从1号城市出发，到$n$号城市去旅游，当在某座城市时，可以将手头剩余的现金全部按照这座城市的汇率转化为旅游金，有$q$次询问，问每次将某座城市的汇率按要求改变后，从1号城市到$n$号城市的最小花费。

输入格式:

第一行包括三个整数，分别表示$n,m,q$。 接下来$m$行，每行四个数$u,v,c,d$，表示从$u$号城市到$v$号城市需要花费$c$的现金或者$d$的旅游金（单向边）。 接下来一行有$n$个整数，依次表示每一座城市的初始汇率$a_i$，即用1元的现金能换多少旅游金。 接着的$q$行，每行两个整数$x_i,a_i'$，表示将$x_i$号城市的汇率变为$a_i'$。

输出格式：

$q$行，表示每次询问后的最小旅游花费。

输入输出样例

6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17

8
8
1

数据规模

$1 \leq n,q \leq 10^5,1 \leq m \leq 2*10^5, 1 \leq u,v,x_i \leq n, 1 \leq c,d,a_i,a_i' \leq 10^9$