부패 폭로

엔로고니아 중앙위원회는 여러 의원으로 이루어져 있다. 정치 체제가 양당제라서 모든 의원은 두 정당 중 하나에 속한다. 하나는 진지한 정당(DSP)이고, 다른 하나는 파티! 파티! 파티(PPP)다.

에드워드는 탐사보도 기자다. 그는 의원이 전부 부패했다는 사실을 알아냈다. 의원마다 정해진 액수의 엔로그머니를 받으면 당적을 옮긴다. 액수는 의원마다 다르지만, 값이 없는 의원은 없다.

정치판이 늘 그렇듯 일부 의원 쌍은 서로 앙숙이다. 앙숙인 두 의원은 같은 정당에 속하기를 절대 받아들이지 않는다. 에드워드는 예산의 일부나 전부를 써서 몇몇 의원의 당적을 옮기고, 그렇게 해서 취재의 확실한 증거를 얻으려고 한다. 이때 앙숙 관계는 지켜야 한다. 돈을 받은 의원이 모두 당적을 옮긴 뒤에도 앙숙인 두 의원은 서로 다른 정당에 속해야 한다.

에드워드는 파장을 최대로 키우고 싶다. 예산을 넘지 않게 쓸 때 DSP에 속할 수 있는 의원 수의 최댓값과, 같은 조건에서 PPP에 속할 수 있는 의원 수의 최댓값을 구하라.

첫째 줄에 네 정수 $D$, $P$, $R$, $B$가 주어진다. 각각 처음에 DSP에 속한 의원 수($1 \le D \le 100$), 처음에 PPP에 속한 의원 수($1 \le P \le 100$), 앙숙 관계의 수($1 \le R \le 2000$), 에드워드의 예산($1 \le B \le 10^4$, 단위는 엔로그머니)이다. DSP 의원에는 $1$번부터 $D$번까지, PPP 의원에는 $1$번부터 $P$번까지 서로 다른 번호가 붙는다.

둘째 줄에 $D$개의 정수 $S_1, S_2, \dots, S_D$가 주어진다. DSP의 $i$번 의원은 $S_i$ 엔로그머니를 받으면 당적을 옮긴다($1 \le S_i \le 100$).

셋째 줄에 $P$개의 정수 $T_1, T_2, \dots, T_P$가 주어진다. PPP의 $j$번 의원은 $T_j$ 엔로그머니를 받으면 당적을 옮긴다($1 \le T_j \le 100$).

다음 $R$개의 줄에는 각각 두 정수 $X$와 $Y$가 주어지며, DSP의 $X$번 의원과 PPP의 $Y$번 의원이 앙숙이라는 뜻이다($1 \le X \le D$, $1 \le Y \le P$). 같은 쌍이 두 번 이상 나올 수 있다.

한 줄에 두 정수를 출력한다. 예산 안에서 DSP에 속할 수 있는 의원 수의 최댓값과, 예산 안에서 PPP에 속할 수 있는 의원 수의 최댓값이다. 두 값은 서로 독립이므로 각각 예산 전액을 쓸 수 있다고 보고 계산한다.