← 返回题目列表

Codeforces · 1150/A

A. 股票套利

中文机器翻译题面 查看原题

欢迎来到 Codeforces 证券交易所!我们现在的限制非常有限,因为我们目前允许交易一只股票,即 Codeforces Ltd。我们希望您仍然能够从市场中获利!

早上有$$$n$$$ 买入股票的机会。其中第 $$$i$$$ 允许您购买任意数量的股票,每份股票的价格为 $$$s_i$$$ bourles。

晚上有 $$$m$$$ 卖出股票的机会。其中第 $$$i$$$ 允许出售任意数量的股票,每份股票的价格为 $$$b_i$$$ bourles。您出售的股票数量不能超过您拥有的股票数量。

现在是早上,您拥有 $$$r$$$ bourles,但没有股票。

晚上之后您最多可以持有多少个布尔尔?

输入

输入的第一行包含三个整数 $$$n, m, r$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq m \leq 30$$$, $$$1 \leq r \leq 1000$$$) — 市场上购买股票的方式数量、市场上出售股票的方式数量以及数量你现在持有的布尔斯。

下一行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$); $$$s_i$$$ 表示以$$$s_i$$$ 布尔的价格购买股票的机会。

以下行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 1000$$$); $$$b_i$$$ 表示以 $$$b_i$$$ 布尔的价格出售股票的机会。

输出

输出一个整数——晚上之后你可以持有的最大布尔数。

示例

输入 #1

3 4 11
4 2 5
4 4 5 4

输出 #1

26

输入 #2

2 2 50
5 7
4 2

输出 #2

50

注意

在第一个示例测试中,您早上喝了 $$$11$$$ 布尔。最好是早上以 $$$2$$$ 布尔的价格买入 $$$5$$$ 股票,然后在晚上以 $$$5$$$ 布尔的价格出售所有股票。很容易验证您晚上后是否会喝到 $$$26$$$ 的布尔斯啤酒。

在第二个示例测试中,最好不要采取任何操作。