Exposing corruption

The Central Committee of Nlogonia is made up of many congress members. The political system has exactly two parties, so every member belongs to one of them: the Deadly Serious Party (DSP) or the Party! Party! Party (PPP).

Edward is an investigative journalist. He found out that every congress member is corrupt and switches parties when offered a certain amount of Nlogmoney. The amount differs from member to member, but no member is without a price.

As usual in politics, some pairs of congress members are rivals. Two rivals never accept belonging to the same party. Edward wants to spend part or all of his budget to make some members switch parties and so collect solid evidence for his investigation. He has to respect the rivalries: after everyone who took the money has switched, two rivals must still belong to different parties.

Edward wants the largest possible impact. Find the maximum number of congress members that can belong to DSP when he spends at most his whole budget, and, under the same condition, the maximum number that can belong to PPP.

The first line contains four integers $D$, $P$, $R$ and $B$: the number of congress members who start in DSP ($1 \le D \le 100$), the number who start in PPP ($1 \le P \le 100$), the number of rivalries ($1 \le R \le 2000$), and Edward's budget in Nlogmoney ($1 \le B \le 10^4$). Members of DSP get distinct numbers from $1$ to $D$, and members of PPP get distinct numbers from $1$ to $P$.

The second line contains $D$ integers $S_1, S_2, \dots, S_D$. Member $i$ of DSP switches parties when offered $S_i$ Nlogmoney ($1 \le S_i \le 100$).

The third line contains $P$ integers $T_1, T_2, \dots, T_P$. Member $j$ of PPP switches parties when offered $T_j$ Nlogmoney ($1 \le T_j \le 100$).

Each of the next $R$ lines contains two integers $X$ and $Y$, meaning that member $X$ of DSP and member $Y$ of PPP are rivals ($1 \le X \le D$, $1 \le Y \le P$). The same pair can appear more than once.

Print one line with two integers: the maximum number of congress members that can belong to DSP within the budget, and the maximum number that can belong to PPP within the budget. The two values are independent, so each one is computed with the whole budget available.