#6511. 「雅礼集训 2018 Day8」B

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定 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

输出格式

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

样例

样例输入 1

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

样例输出 1

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