欢迎来到 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$$$ 的布尔斯啤酒。
在第二个示例测试中,最好不要采取任何操作。