Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare npotions.
Anton has a special kettle, that can prepare one potions in x seconds. Also, he knows spells of two types that can faster the process of preparing potions.
- Spells of this type speed up the preparation time of one potion. There are m spells of this type, the i-th of them costs bi manapoints and changes the preparation time of each potion to ai instead of x.
- Spells of this type immediately prepare some number of potions. There are k such spells, the i-th of them costs di manapoints and instantly create ci potions.
Anton can use no more than one spell of the first type and no more than one spell of the second type, and the total number of manapoints spent should not exceed s. Consider that all spells are used instantly and right before Anton starts to prepare potions.
Anton wants to get to the next level as fast as possible, so he is interested in the minimum number of time he needs to spent in order to prepare at least n potions.
The first line of the input contains three integers n, m, k (1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105) — the number of potions, Anton has to make, the number of spells of the first type and the number of spells of the second type.
The second line of the input contains two integers x and s (2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109) — the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.
The third line contains m integers ai (1 ≤ ai < x) — the number of seconds it will take to prepare one potion if the i-th spell of the first type is used.
The fourth line contains m integers bi (1 ≤ bi ≤ 2·109) — the number of manapoints to use the i-th spell of the first type.
There are k integers ci (1 ≤ ci ≤ n) in the fifth line — the number of potions that will be immediately created if the i-th spell of the second type is used. It's guaranteed that ci are not decreasing, i.e. ci ≤ cj if i < j.
The sixth line contains k integers di (1 ≤ di ≤ 2·109) — the number of manapoints required to use the i-th spell of the second type. It's guaranteed that di are not decreasing, i.e. di ≤ dj if i < j.
Print one integer — the minimum time one has to spent in order to prepare n potions.
20 3 2 10 99 2 4 3 20 10 40 4 15 10 80
20
20 3 2 10 99 2 4 3 200 100 400 4 15 100 800
200
In the first sample, the optimum answer is to use the second spell of the first type that costs 10 manapoints. Thus, the preparation time of each potion changes to 4 seconds. Also, Anton should use the second spell of the second type to instantly prepare 15 potions spending 80manapoints. The total number of manapoints used is 10 + 80 = 90, and the preparation time is 4·5 = 20 seconds (15 potions were prepared instantly, and the remaining 5 will take 4 seconds each).
In the second sample, Anton can't use any of the spells, so he just prepares 20 potions, spending 10 seconds on each of them and the answer is 20·10 = 200.
题意：
要制作n瓶药水，有m种魔法A，k种魔法B；
每制作一瓶药水需要的标准时间是x，共有s点魔法值；
对于魔法A来说，花费b[i]点魔法值能把药水的标准时间降为a[i]；
对于魔法B来说，花费d[i]点魔法值能直接完成c[i]瓶药水；
A和B都只能使用一次，即只能使用Ａ的一种方案和Ｂ的一种方案；
求制作n瓶药水的最小时间是多少；
思路： 二分。。二分可以消去的药品，因为这样可以直接计算出公式，就算题目没有给排序，也要自己排序，然后二分，消去多少瓶，那么剩下的*价值就是总的价值。除非是消耗法力值多，否则不可能一种也不用，第二种肯定可以用的，第一种就不一定了，所以让a[0] = x,b[0] = 0;
因为两种法术各自只能取一种，所以可以想到两个for暴力，n^2复杂度必然超时，题目强调了法术2是已经排好序的，自然而然的可以想到二分，就把复杂度降到了nlogn。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3fffffff;
ll a[maxn], b[maxn], c[maxn], d[maxn];
int main()
{
ll n, m, k, x, s;
while(cin >> n >> m >> k >> x >> s)
{
ll ans = n*x; //这里可能爆int ，所以要这样
a[0] = x;
for(int i = 1; i <= m; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1; i <= k; i++) cin >> c[i];
for(int i = 1; i <= k; i++) cin >> d[i];
for(int i = 0; i <= m; i++)
{
if(b[i] > s) continue;
ll l = 1, r = k, temp = 0, mid;
while(l <= r)
{
mid = (l+r)/2;
if(d[mid] + b[i] <= s) {temp = mid; l = mid + 1;} //这里想一下
else r = mid - 1;
}
ans = min(ans, a[i]*(n-c[temp]));
}
cout << ans << endl;
}
return 0;
}