P2113 Watching Soccer and Dating

The 2014 Brazil World Cup has kicked off. The whole city is full of World Cup fever, and businesses are making a fortune from it. Xiao Ming and Xiao Hong also take this opportunity to strengthen their relationship.

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$.

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 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`.

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