题目描述

欢迎来到 Codeforces 股票交易所！目前我们只能交易一只股票——Codeforces Ltd.，所以功能还比较有限。希望你依然能从市场中获利。

早上有 $n$ 次买入股票的机会。第 $i$ 次机会可以以 $s_i$ 布尔的价格，买入任意数量的股票。

晚上有 $m$ 次卖出股票的机会。第 $i$ 次机会可以以 $b_i$ 布尔的价格，卖出任意数量的股票，但你不能卖出超过你持有的股票数量。

现在是早上，你手上有 $r$ 布尔，没有任何股票。

请问，经过一天交易后，你最多能拥有多少布尔？

输入格式

输入的第一行包含三个整数 $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$ 布尔的价格卖出股票的机会。

输出格式

输出一个整数，表示经过一天交易后你最多能拥有的布尔数。

说明/提示

在第一个样例中，你早上有 $11$ 布尔。最优策略是在早上以 $2$ 布尔的价格买入 $5$ 股股票，然后在晚上以 $5$ 布尔的价格全部卖出。这样你晚上将拥有 $26$ 布尔。

在第二个样例中，最优策略是不进行任何操作。

由 ChatGPT 4.1 翻译

样例

3 4 11
4 2 5
4 4 5 4

26

2 2 50
5 7
4 2

50