luogu#P2113. 看球泡妹子
看球泡妹子
题目背景
2014 年巴西世界杯开幕了,现在满城皆是世界杯,商家们利用它大赚一笔,小明和小红也借此机会增进感情。
题目描述
本届世界杯共有 支球队, 场比赛。男球迷小明喜欢看比赛,女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为 ,在小红眼里的帅哥数量为 。
每场比赛有两个球队对抗,它们的编号分别是 和 。小明认为一场比赛的精彩度等于两队实力的乘积,小红则认为是两队帅哥数量之和。
由于体力的限制,他们最多只能看 场比赛。当然,只要看比赛,两个人一定会一起看。小明作为男生,理应迁就一下女生,所以,请你写一个程序,求出小红看到比赛的精彩度总和不小于 的情况下,小明看到比赛的精彩度的最大总和。
输入格式
第一行包含四个正整数 。
第二行有 个用空格隔开的正整数 。
第三行有 个用空格隔开的正整数 。
接下来 行,每行两个正整数 。
输出格式
一行,一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求,输出 -1
。
4 3 2 5
2 2 1 3
1 1 1 2
1 2
2 3
3 4
7
提示
数据范围与约定
- 对于 数据,。
- 对于 数据,,,,。