luogu#P2113. 看球泡妹子

看球泡妹子

题目背景

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

题目描述

本届世界杯共有 nn 支球队,mm 场比赛。男球迷小明喜欢看比赛,女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为 aia_i,在小红眼里的帅哥数量为 bib_i

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

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

输入格式

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

第二行有 nn 个用空格隔开的正整数 aia_i

第三行有 nn 个用空格隔开的正整数 bib_i

接下来 mm 行,每行两个正整数 pi,qip_i,q_i

输出格式

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

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

提示

数据范围与约定

  • 对于 20%20\% 数据,1n,m,k51 \le n,m,k \le 5
  • 对于 100%100\% 数据,1n1001 \le n \le 1001km1001 \le k \le m \le 1001ai,bi101 \le a_i,b_i \le 101c1031 \le c \le 10^3