A Stock Arbitraging

迈不过友情╰ 2022-04-25 01:14 103阅读 0赞

A. Stock Arbitraging

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

3 4 11
    4 2 5
    4 4 5 4

output

Copy

input

Copy

2 2 50
    5 7
    4 2

output

Copy

Note

In the first example test, you have 1111 bourles in the morning. It's optimal to buy 55 shares of a stock at the price of 22 bourles in the morning, and then to sell all of them at the price of 55bourles 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.

题意：早上给你n只你可以买入的股票，晚上给你m只可以卖出的股票，你有r元，第二排就是n只早上股票的价格和第三排晚上m只股票能够卖出的价格。到晚上后你最多有多少钱？

题解：为了使最后钱最多，肯定早上买最低的股票，然后晚上把这些股票以最高价格卖出，就能价格最大，但是样例二这种就是如果早上买入最低的价格如果高于晚上卖出最高的价格，肯定就不买，毕竟亏本的不会去做。

c++：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,m,r,x,minn=1100,maxn=0;
        cin>>n>>m>>r;
        for(int i=0; i<n; i++)
            cin>>x,minn=min(minn,x);
    
        for(int i=0; i<m; i++)
            cin>>x,maxn=max(maxn,x);
        if(minn>=maxn)
            cout<<r<<endl;
        else cout<<r/minn*maxn+r%minn<<endl;
        return 0;
    }

python：

R=lambda:map(int,input().split())
    n,m,r=R()
    minn,maxn=(min(R()),max(R()))
    print(r//minn*maxn+r%minn if maxn>minn else r)
    #print(r+max(0,r//minn*(maxn-minn)))