题目描述

给定 $n$ 个待安装的软件包，每个软件包有一个安装时间 $t_i$。

给定一个 $n$ 个点 $m$ 条边的有向无环图代表软件包之间的依赖关系（可能存在重边）。一条从 $u$ 到 $v$ 的有向边代表软件包 $v$ 必须在软件包 $u$ 安装完成之后开始安装。在满足这个上述条件的前提下，没有依赖关系的软件包可以并行安装。

对于每个软件包 $i$ 都可以用 $c_i$ 的代价将其安装时间减 $1$。同一个软件包可以多次减 $1$，但不可以减为负数。

现在，给定一个预算 $w$，求在支出的代价不大于 $w$ 的前提下，安装完所有软件包需要的最小时间。

输入格式

第一行三个整数 $n, m, w$。

第二行 $n$ 个整数 $t_i$，表示每个软件包的安装时间。

第三行 $n$ 个整数 $c_i$，表示将每个软件包安装时间减 $1$ 的代价。

接下来 $m$ 行，每行两个整数 $u, v$，表示软件包 $v$ 依赖软件包 $u$。

输出格式

输出一行一个整数表示最小时间。

样例

input

10 7 12
1 1 2 2 3 3 2 1 3 2
4 6 10 5 1 10 5 1 5 9
8 10
7 8
5 6
3 9
1 2
9 10
3 4

output

5

数据范围与提示

对于全部数据，$1 \leq n \leq 55, 1 \leq m \leq 400, 1 \leq t_i \leq 10^3, 1 \leq w_i \leq 10^4$。

• 子任务 $\rm 1(points: 20)$：$n \leq 10, t_i \leq 3, c_i \leq 10$
• 子任务 $\rm 2(points: 30)$：$n \leq 55, t_i \leq 50, c_i \leq 10^4$
• 子任务 $\rm 3(points: 20)$：$n \leq 35$
• 子任务 $\rm 4(points: 30)$：$n \leq 55$