【CodeForces - 1150A】Stock Arbitraging (贪心,水题)

题干:

Welcome to Codeforces Stock Exchange! We're pretty limited now as we currently allow trading on one stock, Codeforces Ltd. We hope you'll still be able to make profit from the market!

In the morning, there are nn opportunities to buy shares. The ii-th of them allows to buy as many shares as you want, each at the price of sisi bourles.

In the evening, there are mm opportunities to sell shares. The ii-th of them allows to sell as many shares as you want, each at the price of bibi bourles. You can't sell more shares than you have.

It's morning now and you possess rr bourles and no shares.

What is the maximum number of bourles you can hold after the evening?

Input

The first line of the input contains three integers n,m,rn,m,r (1≤n≤301≤n≤30, 1≤m≤301≤m≤30, 1≤r≤10001≤r≤1000) — the number of ways to buy the shares on the market, the number of ways to sell the shares on the market, and the number of bourles you hold now.

The next line contains nn integers s1,s2,…,sns1,s2,…,sn (1≤si≤10001≤si≤1000); sisi indicates the opportunity to buy shares at the price of sisi bourles.

The following line contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤10001≤bi≤1000); bibi indicates the opportunity to sell shares at the price of bibi bourles.

Output

Output a single integer — the maximum number of bourles you can hold after the evening.

Examples

Input

3 4 11
4 2 5
4 4 5 4

Output

26

Input

2 2 50
5 7
4 2

Output

50

Note

In the first example test, you have 1111 bourles in the morning. It's optimal to buy 55shares of a stock at the price of 22 bourles in the morning, and then to sell all of them at the price of 55 bourles in the evening. It's easy to verify that you'll have 2626 bourles after the evening.

In the second example test, it's optimal not to take any action.

解题报告:

简单的贪心,,刚开始读错题了还以为是个背包。。(cfA题出背包??)写完发现是个完全背包,所以也是可以贪心的,想了想放到A题还是有些合理的,,再看样例解释发现不对,,比想象中的水多了、、、就写了、、

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int dp[MAX],dpp[MAX],n,m,r,a[MAX],b[MAX];
int main()
{
	cin>>n>>m>>r;
	for(int i = 1; i<=n; i++) cin>>a[i];
	for(int i = 1; i<=m; i++) cin>>b[i];
	int minn = *min_element(a+1,a+n+1);
	int maxx = *max_element(b+1,b+m+1);
	int ci = r/minn;
	printf("%d\n",max(r,r + (maxx-minn)*ci));
	
//	for(int i = 0; i<=r; i++) dpp[i] = r;//设置初始状态,dpp[i]代表有i块钱时可以拥有的最大钱数,因为啥都不买所以拥有的是r
//	for(int i = 1; i<=min(n,m); i++) {
//		for(int j = a[i]; j<=r; j++) {
//			if(dp[j-a[i]] + b[i]-a[i] > dp[j]) {
//				dp[j] = dp[j-a[i]] + b[i]-a[i];
//				dpp[j] = dpp[j-a[i]] + b[i]-a[i];
//			}
//		}
//	}
//	printf("%d\n",dpp[r]);

	return 0 ;
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务