Maximizing Match Excitement

In this problem, there are $n$ teams and $m$ matches in this World Cup. For each team i, two values are given: the strength $a_i$ (according to Xiao Ming) and the number of handsome players $b_i$ (according to Xiao Hong).

Each match is played between two teams with indices $p_i$ and $q_i$. Xiao Ming considers the excitement of a match as the product of the two teams' strengths, i.e. $a_{p_i} \times a_{q_i}$, while Xiao Hong considers the excitement as the sum of the handsome counts, i.e. $b_{p_i} + b_{q_i}$.

They can watch at most $k$ matches together. Xiao Hong requires that the total excitement she sees (i.e. the sum over the chosen matches of $b_{p_i}+b_{q_i}$) is at least $c$. Under this constraint, your task is to choose a subset of matches (no more than $k$ matches) so that the total excitement for Xiao Ming (i.e. the sum over the chosen matches of $a_{p_i}\times a_{q_i}$) is maximized. If no valid selection exists, output -1.

Note: If the sum of Xiao Hong's excitement does not reach $c$, the selection is invalid.

inputFormat

The input begins with a line containing four integers n m k c:

• n: the number of teams
• m: the number of matches
• k: the maximum number of matches they can watch
• c: the minimum total excitement required by Xiao Hong

The next line contains n integers: a1 a2 ... an, where ai is the strength of team i.

The next line contains n integers: b1 b2 ... bn, where bi is the number of handsome players in team i.

The following m lines each contain two integers: pi qi, representing a match between team pi and team qi (teams are 1-indexed).

outputFormat

Output a single integer: the maximum total excitement for Xiao Ming if there exists a selection of matches (no more than k) that makes Xiao Hong's total excitement at least c. If no valid selection exists, output -1.

sample

3 3 2 10
1 2 3
1 3 5
1 2
1 3
2 3

9