Description

There are $n$ teams and $m$ matches in this World Cup. Xiao Ming, a male fan, likes watching matches, while Xiao Hong, a female fan, likes watching handsome guys. For each team, its strength in Xiao Ming’s view is $a_i$, and the number of handsome guys in Xiao Hong’s view is $b_i$.

Each match is between two teams with indices $p_i$ and $q_i$. Xiao Ming thinks the excitement of a match equals the product of the two teams’ strengths, while Xiao Hong thinks it equals the sum of the two teams’ numbers of handsome guys.

Due to limited energy, they can watch at most $k$ matches. Of course, if they watch matches, they will always watch together. As a gentleman, Xiao Ming should compromise, so please write a program to find the maximum possible total excitement for Xiao Ming, subject to the constraint that Xiao Hong’s total excitement is at least $c$.

Input Format

The first line contains four positive integers $n, m, k, c$.

The second line contains $n$ positive integers $a_i$ separated by spaces.

The third line contains $n$ positive integers $b_i$ separated by spaces.

The next $m$ lines each contain two positive integers $p_i, q_i$.

Output Format

Output a single line containing a single positive integer: the maximum total excitement that Xiao Ming can get. If it is impossible to satisfy Xiao Hong’s requirement, output -1.

4 3 2 5
2 2 1 3
1 1 1 2
1 2
2 3
3 4

7

Hint

Constraints

• For $20\%$ of the testdata, $1 \le n, m, k \le 5$.
• For $100\%$ of the testdata, $1 \le n \le 100$, $1 \le k \le m \le 100$, $1 \le a_i, b_i \le 10$, $1 \le c \le 10^3$.

Translated by ChatGPT 5