题目描述
给定 n 个待安装的软件包,每个软件包有一个安装时间 ti。
给定一个 n 个点 m 条边的有向无环图代表软件包之间的依赖关系(可能存在重边)。一条从 u 到 v 的有向边代表软件包 v 必须在软件包 u 安装完成之后开始安装。在满足这个上述条件的前提下,没有依赖关系的软件包可以并行安装。
对于每个软件包 i 都可以用 ci 的代价将其安装时间减 1。同一个软件包可以多次减 1,但不可以减为负数。
现在,给定一个预算 w,求在支出的代价不大于 w 的前提下,安装完所有软件包需要的最小时间。
输入格式
第一行三个整数 n,m,w。
第二行 n 个整数 ti,表示每个软件包的安装时间。
第三行 n 个整数 ci,表示将每个软件包安装时间减 1 的代价。
接下来 m 行,每行两个整数 u,v,表示软件包 v 依赖软件包 u。
输出格式
输出一行一个整数表示最小时间。
样例
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
5
数据范围与提示
对于全部数据,1≤n≤55,1≤m≤400,1≤ti≤103,1≤wi≤104。
- 子任务 1(points:20):n≤10,ti≤3,ci≤10
- 子任务 2(points:30):n≤55,ti≤50,ci≤104
- 子任务 3(points:20):n≤35
- 子任务 4(points:30):n≤55