Maximizing Profit with Technology and Product Dependencies

You are given a market scenario where launching certain products will yield profit, but each product requires a set of technologies. There are two ways to acquire a technology:

1. Purchase it directly at a cost of $f_j$. This method does not require any prerequisites.

2. Develop (R&D) it at a cost of $h_j$, but developing technology $j$ is only possible if all of its prerequisite technologies have already been acquired (by either method).

In addition, there are dependencies between products and technologies. There are $m$ products; launching the $i$th product earns a profit of $g_i$, but it can only be launched if all its prerequisite technologies are acquired. You are given $p$ pairs $(u,v)$ meaning that technology $u$ is required before launching product $v$.

Furthermore, there are $n$ technologies and $q$ pairs $(a,b)$ representing technology–technology dependency: technology $a$ is a prerequisite for technology $b$ for the purpose of R&D acquisition. Note that the technology–technology dependency forms a directed acyclic graph (DAG), so no cycles occur.

A plan consists of selecting some products to launch (and hence acquiring the necessary technologies) and deciding for each required technology whether to purchase it or develop it. If a technology is acquired by development, all of its R&D prerequisites (according to the $q$ relations) must also be acquired by development. However, you may always opt to purchase a technology regardless of whether its prerequisites have been acquired.

The total profit is defined as the sum of the profits of the launched products minus the total cost of the technologies used. When a technology is required by more than one product, its cost is only paid once.

Your task is to output the maximum achievable profit.

Formally, let $S$ be the set of launched products and let $T$ be the set of required technologies (which must at least cover the prerequisites for every product in $S$). For each technology $j \in T$, you may acquire it by purchase at cost $f_j$, or by R&D at cost $h_j$ provided that every technology $a$ with a dependency $(a, j)$ is also acquired by R&D. The goal is to maximize: [ \text{Profit} = \sum_{i\in S} g_i - \sum_{j\in T} \text{cost}(j), ] where ( \text{cost}(j) ) is chosen as described.

A common way to solve this problem is to reduce it to a maximum closure (or minimum cut) problem in a directed graph. In one typical formulation, you construct a graph where:

• Each product $i$ is represented with a profit (positive weight) $g_i$, and an edge is added from the source to product $i$ with capacity $g_i$.
• Each technology $j$ is represented with a cost (negative weight) of $-f_j$, and an edge is added from technology $j$ to the sink with capacity $f_j$.
• For every product–technology dependency $(u,v)$ (meaning technology $u$ is required for product $v$), add an edge from product $v$ to technology $u$ with infinite capacity.
• For every technology–technology dependency $(a, b)$ (meaning technology $a$ is a prerequisite for developing technology $b$), add an edge from technology $b$ to technology $a$ with capacity $\max(0, f_b - h_b)$. This edge effectively models the benefit (discount) of using R&D for technology $b$ when its prerequisite $a$ is also acquired by R&D.

The maximum closure value of this graph is equal to the maximum achievable profit. (Note that all formulas involving costs and profits must be written using LaTeX formatting.)

inputFormat

The input begins with four integers $m$, $n$, $p$, and $q$, where:

• $m$ is the number of products.
• $n$ is the number of technologies.
• $p$ is the number of product dependencies.
• $q$ is the number of technology dependencies.

The second line contains $m$ integers, $g_1, g_2, \ldots, g_m$, representing the profit of each product.

The third line contains $n$ integers, $f_1, f_2, \ldots, f_n$, representing the purchase cost for each technology.

The fourth line contains $n$ integers, $h_1, h_2, \ldots, h_n$, representing the R&D cost for each technology.

Then follow $p$ lines, each containing two integers $u$ and $v$, indicating that technology $u$ is a prerequisite for product $v$.

Finally, there are $q$ lines, each containing two integers $a$ and $b$, indicating that technology $a$ is a prerequisite (for R&D) for technology $b$.

All indices are 1-indexed.

outputFormat

Output a single integer: the maximum profit achievable.

sample

1 1 1 0
10
5
3
1 1

5