Seeing several large model startups receive high financing recently, you, as a master of "alchemy" (machine learning), feel restless and decide to enter the market to develop your own products.

After some analysis, you find that there are $m$ types of products that will sell well upon release, with the $i$-th product expected to generate a profit of $g_i$. These $m$ products involve $n$ types of technologies. There are $p$ technology-product dependency relations $(u, v)$, meaning that technology $u$ is a prerequisite for product $v$. For each product, you must acquire all of its prerequisite technologies before you can release it.

For the $j$-th technology, you can choose to spend $f_j$ to purchase it directly from another company, or spend $h_j$ to acquire it through research. Research has certain conditions: given $q$ technology-technology dependency relations $(a, b)$, meaning that technology $a$ is a prerequisite for technology $b$, you must acquire all prerequisites of technology $j$ before you can acquire technology $j$ through research. If a technology has no prerequisites, you can acquire it directly through research. It is guaranteed that the technology-technology dependency relations form a directed acyclic graph, meaning there are no circular dependencies (and naturally no self-loops).

The profit of a plan is the sum of the profits of the released products minus the total cost of the acquired technologies. Now, as a businessman, you want to research some technologies and release some products to maximize your profit. For simplicity, you only need to output the maximum profit value.

Input

The first line contains four positive integers $n, m, p, q$, where $2 \le n \le 10^2$, $1 \le m \le 10^2$, $1 \le p \le nm$, and $1 \le q \le \frac{n(n-1)}{2}$, representing the total number of technologies, the total number of products, the total number of technology-product dependencies, and the total number of technology-technology dependencies, respectively.

The next line contains $n$ integers $f_i$, representing the cost to purchase the $i$-th technology directly.

The next line contains $n$ integers $h_i$, representing the cost to acquire the $i$-th technology through research, given its prerequisites.

The next line contains $m$ integers $g_i$, representing the profit obtained after releasing the $i$-th product.

The next $p$ lines each contain two integers $u_i, v_i$, representing a technology-product dependency $(u_i, v_i)$, where $1 \le u_i \le n$ and $1 \le v_i \le m$. All $(u_i, v_i)$ pairs are distinct.

The next $q$ lines each contain two integers $a_i, b_i$, representing a technology-technology dependency $(a_i, b_i)$, where $1 \le a_i \ne b_i \le n$. All $(a_i, b_i)$ pairs are distinct, and they do not form any circular dependencies.

It is guaranteed that all input numbers are non-negative integers not exceeding $10^9$.

Output

Output a single integer representing the maximum profit of the optimal plan.

Examples

Input 1

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

Output 1

8

Note 1

The optimal plan is to research technology 1, purchase technology 3, and research technology 4. At this point, we can release products 1, 4, and 5. The profit is $(2+8+8)-(1+6+3)=8$.