Stock Arbitraging
Contest: Codeforces Round 556 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

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 $$$n$$$ opportunities to buy shares. The $$$i$$$-th of them allows to buy as many shares as you want, each at the price of $$$s_i$$$ bourles.

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

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

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

Input format:
The first line of the input contains three integers $$$n, m, r$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq m \leq 30$$$, $$$1 \leq r \leq 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 $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$); $$$s_i$$$ indicates the opportunity to buy shares at the price of $$$s_i$$$ bourles.

The following line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 1000$$$); $$$b_i$$$ indicates the opportunity to sell shares at the price of $$$b_i$$$ bourles.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example test, you have $$$11$$$ bourles in the morning. It's optimal to buy $$$5$$$ shares of a stock at the price of $$$2$$$ bourles in the morning, and then to sell all of them at the price of $$$5$$$ bourles in the evening. It's easy to verify that you'll have $$$26$$$ bourles after the evening.

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

Example input:
3 4 11
4 2 5
4 4 5 4

Example output:
26

Example input:
2 2 50
5 7
4 2

Example output:
50

Editorial:
The main observation is that we always want to buy shares as cheaply as possible, and sell them as expensively as possible. Therefore, we should pick the lowest price at which we can buy shares $$$s_{\min} = \min(s_1, s_2, \dots, s_n)$$$, and the highest price at which we can sell the shares $$$b_{\max} = \max(b_1, b_2, \dots, b_m)$$$. Now, we have two cases:
• If $$$s_{\min} < b_{\max}$$$, it's optimal to buy as many shares and possible in the morning and sell them all in the evening. We can buy as many as $$$\left\lfloor \frac{r}{s_{\min}} \right\rfloor$$$ shares and gain $$$b_{\max} - s_{\min}$$$ bourles profit on each of them. Therefore, the final balance is $$$r + \left\lfloor \frac{r}{s_{\min}} \right\rfloor (b_{\max} - s_{\min})$$$.
• If $$$s_{\min} \geq b_{\max}$$$, we're not gaining any profit on the shares and therefore we shouldn't care about trading stocks at all. The final balance is then $$$r$$$.
The solution can be therefore implemented in $$$O(n + m)$$$ time. However, the constraints even allowed brute-forcing the seller, the buyer and the amount of stock we're buying in $$$O(nmr)$$$ time.
Note that many programming languages have routines for finding the minima/maxima of the collections of integers: e.g. min_element in C++, Collections.min in Java, or min in Python. This should make the code shorter and quicker to write.