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

「雅礼集训 2018 Day8」B

题目描述

给定 nn 个待安装的软件包,每个软件包有一个安装时间 tit_i

给定一个 nn 个点 mm 条边的有向无环图代表软件包之间的依赖关系(可能存在重边)。一条从 uuvv 的有向边代表软件包 vv 必须在软件包 uu 安装完成之后开始安装。在满足这个上述条件的前提下,没有依赖关系的软件包可以并行安装。

对于每个软件包 ii 都可以用 cic_i 的代价将其安装时间减 11。同一个软件包可以多次减 11,但不可以减为负数。

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

输入格式

第一行三个整数 n,m,wn, m, w

第二行 nn 个整数 tit_i,表示每个软件包的安装时间。

第三行 nn 个整数 cic_i,表示将每个软件包安装时间减 11 的代价。

接下来 mm 行,每行两个整数 u,vu, v,表示软件包 vv 依赖软件包 uu

输出格式

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

样例

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 \leq n \leq 55, 1 \leq m \leq 400, 1 \leq t_i \leq 10^3, 1 \leq w_i \leq 10^4$。

  • 子任务 1(points:20)\rm 1(points: 20)n10,ti3,ci10n \leq 10, t_i \leq 3, c_i \leq 10
  • 子任务 2(points:30)\rm 2(points: 30)n55,ti50,ci104n \leq 55, t_i \leq 50, c_i \leq 10^4
  • 子任务 3(points:20)\rm 3(points: 20)n35n \leq 35
  • 子任务 4(points:30)\rm 4(points: 30)n55n \leq 55