Migrated from Lutece 2957 灵山、秋叶、风之歌

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

秋日的某一天，东风谷早苗从神社出发，要去人间之里收集信仰。

人间之里由 $n$ 个村庄组成，编号从 $1$ 到 $n$ ，神社编号为 $0$，有 $m$ 条单向道路连接各个地点。

每个村庄有一个信仰值 $a_i$，早苗每次拜访某个村庄，无论是第几次拜访，都能获得 $a_i$ 的信仰值。由于某些村庄认为信仰是虚幻的，$a_i$ 可能为负数。早苗想收集大于等于 $k$ 的信仰值，于是在村庄之间游走拜访。

早苗每次走一条道路需要花费 $1$ 点灵力，她还可以在任意时间和地点使用传送（包括从神社出发），传送到任意村庄 $i$，但要花费 $d_i$ 点灵力。

请算出早苗收集大于等于 $k$ 的信仰至少需要花费多少灵力。

数据保证至少一个村庄信仰值为正数，你可以选择在这个村庄原地传送，直到信仰值和大于等于 $k$ ，因此答案一定存在。

Input

第一行三个整数 $n,m,k$，村庄数，道路数，需要收集的信仰值；

第二行 $n$ 个整数 $a_i$；

第三行 $n$ 个整数 $d_i$；

接下来 $m$ 行每行两个整数 $x_i,y_i$，有一条从 $x_i$ 到 $y_i$ 的单向道路，神社编号为零。（无自环，可能有重边）

Output

一个数，需要花费的最小灵力值。

Samples

6 8 18
2 3 -4 -3 -1 10
6 7 4 5 6 8
0 1
0 2
1 2
2 3
3 1
4 5
5 6
6 4

11

Constraints

$1 \leq n\leq 200，1\leq m \leq 10^5，1\leq k \leq 10^7;$

$0 \leq x_i\neq y_i \leq n;$

$-10^7\leq a_i\leq 10^7，2 \leq d_i \leq 100$。

Resources

2023 UESTC ICPC Training for Graph