题目描述

看到近期若干家大模型创业公司获得高额融资，作为炼丹大师的你心痒难耐，决定入局，亲自下场搞产品。

经过一段时间的梳理，你发现当前共有 $m$ 种产品推出后将会大卖，其中第 $i$ 个产品推出之后预期获得 $g_i$ 的收益。这 $m$ 种产品涉及 $n$ 种技术：共有 $p$ 条技术-产品依赖关系 $(u,v)$ ，表示第 $u$ 个技术是第 $v$ 个产品的前置技术。对于每个产品，你必须获得它的全部前置技术之后才能推出。

对于第 $j$ 个技术，你可以选择花费 $f_j$ 的代价直接从其他公司购买获得，或者花费 $h_j$ 的代价通过研发获得。研发需要一定的条件：给出 $q$ 条技术-技术依赖关系 $(a,b)$ ，表示第 $a$ 个技术是第 $b$ 个技术的前置技术，那么必须在获得了技术 $j$ 的所有前置技术后才能通过研发获得技术 $j$ 。若某个技术没有前置技术，那么你可以直接通过研发获得。保证技术-技术依赖关系构成一个有向无环图，即不会发生循环依赖（自然不会有自环）。

一个方案的收益为推出的产品的收益总和减去获得的技术的代价总和。现在，作为一个商人，你希望研究一些技术、推出一些产品，最大化你获得的收益。为简单起见，你只要输出最大的收益值。

输入格式

输入的第一行包含四个正整数 $n,m,p,q$，保证 $2 \le n \le 100, 1 \le m \le 100, 1 \le p\leq nm, 1 \le q\leq \frac{n(n-1)}{2}$ ，分别表示技术总数、产品总数、技术-产品依赖关系总数以及技术-技术依赖关系总数。

接下来一行 $n$ 个整数 $f_i$ ，表示直接购买第 $i$ 个技术的代价。

接下来一行 $n$ 个整数 $h_i$ ，表示在前置技术基础上研究第 $i$ 个技术的代价。

接下来一行 $m$ 个整数 $g_i$，表示第 $i$ 个产品推出之后获得的收益。

接下来 $p$ 行，第 $i$ 行两个整数 $u_i,v_i$ ，表示技术-产品依赖关系 $(u_i,v_i)$，保证 $1 \le u_i \le n$，$1 \le v_i \le m$，输入的所有 $(u_i,v_i)$ 两两不同。

接下来 $q$ 行，第 $i$ 行两个整数 $a_i,b_i$ ，表示技术-技术依赖关系 $(a_i,b_i)$，保证 $1 \le a_i \ne b_i \le n$，输入的所有 $(a_i,b_i)$ 两两不同，且不构成循环依赖。

保证所有输入数字均为不超过 $10^9$ 的非负整数。

输出格式

输出一个整数表示收益最大方案的收益。

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

8

提示

最优方案是依次研究技术 1，购买技术 3，研究技术 4，这时我们就能推出产品 1、4、5 了。此时收益为 $(2+8+8)-(1+6+3)=8$。

来源与致谢

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public