题目背景

2014 年巴西世界杯开幕了，现在满城皆是世界杯，商家们利用它大赚一笔，小明和小红也借此机会增进感情。

题目描述

本届世界杯共有 $n$ 支球队，$m$ 场比赛。男球迷小明喜欢看比赛，女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为 $a_i$，在小红眼里的帅哥数量为 $b_i$。

每场比赛有两个球队对抗，它们的编号分别是 $p_i$ 和 $q_i$。小明认为一场比赛的精彩度等于两队实力的乘积，小红则认为是两队帅哥数量之和。

由于体力的限制，他们最多只能看 $k$ 场比赛。当然，只要看比赛，两个人一定会一起看。小明作为男生，理应迁就一下女生，所以，请你写一个程序，求出小红看到比赛的精彩度总和不小于 $c$ 的情况下，小明看到比赛的精彩度的最大总和。

输入格式

第一行包含四个正整数 $n,m,k,c$。

第二行有 $n$ 个用空格隔开的正整数 $a_i$。

第三行有 $n$ 个用空格隔开的正整数 $b_i$。

接下来 $m$ 行，每行两个正整数 $p_i,q_i$。

输出格式

一行，一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求，输出 -1。

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

7

提示

数据范围与约定

• 对于 $20\%$ 数据，$1 \le n,m,k \le 5$。
• 对于 $100\%$ 数据，$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$。