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。

• 对于 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。

luogu