DAG 路径最小化

描述

给定一张有 $n$ 个点 $m$ 条边的 $\text{DAG}$ 图，第 $i$ 个点的点权为 $a_i$。

你可以任意多次花费 $c_i$ 使该点点权减 $1$（不能为负）。

现在你最多可以花费 $x$ ，请最小化所有路径的权值的最大值。

路径的权值被定义为：一条路径上所有经过的点的点权和。

格式

输入

第一行包含三个整数 $n, m, x$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

第三行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一条从 $u$ 到 $v$ 的有向边。

输出

输出一个整数，表示最小可能的最大路径权值。

样例

样例输入

4 4 3
5 3 2 4
2 1 3 2
1 2
1 3
2 4
3 4

样例输出

6

限制

• $1 \leq n \leq 50$
• $1 \leq m \leq n(n-1)/2$
• $1 \leq a_i, c_i \leq 10^9$
• $1 \leq x \leq 10^9$

提示

考虑二分答案，然后判断是否可行。可行性可以通过贪心从终点向起点递推来判断。