【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

Input

2 2 50
5 7
4 2

Output

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 ;
}