AT_m_solutions2020_d Road to Millionaire

M 君为了成为亿万富翁，打算从明天开始的 $N$ 天里通过投资赚钱。现在他手头有 $1000$ 日元，并且没有持有任何股票。值得注意的是，他所在的国家只发行了一种股票。 他是全国闻名的未来预知能力者，已经知道接下来 $N$ 天的股票价格如下： - 第 $1$ 天的股价为 $A_1$ 日元，第 $2$ 天的股价为 $A_2$ 日元，……，第 $N$ 天的股价为 $A_N$ 日元。 在第 $i$ 天，**在所持现金和股票数量的范围内**，M 君可以进行如下任意次数的交易。某些天也可以选择不进行任何交易。 - 股票购买：支付 $A_i$ 日元，获得 $1$ 股股票。 - 股票卖出：卖出 $1$ 股股票，获得 $A_i$ 日元。 请问，M 君如果进行最优的交易操作，他最终最多能拥有多少日元？

输入以如下格式从标准输入读入。 > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出 M 君最终可能拥有的最大金额，结果为整数。

## 限制条件 - $2 \leq N \leq 80$ - $100 \leq A_i \leq 200$ - 输入均为整数 ## 样例解释 1 在本样例中，M 君将在 $7$ 天内进行股票交易。例如，按照以下方式操作，最终可以获得 $1685$ 日元： - 初始时，M 君有 $1000$ 日元，没有股票。 - 第 $1$ 天：进行 $10$ 次股票购买。用 $1000$ 日元买入 $10$ 股，现金变为 $0$ 日元。 - 第 $2$ 天：进行 $7$ 次股票卖出。卖出 $7$ 股，获得 $910$ 日元，现金变为 $910$ 日元。 - 第 $3$ 天：进行 $3$ 次股票卖出。卖出 $3$ 股，获得 $390$ 日元，现金变为 $1300$ 日元。 - 第 $4$ 天：不进行任何操作。 - 第 $5$ 天：进行 $1$ 次股票购买。用 $115$ 日元买入 $1$ 股，现金变为 $1185$ 日元。 - 第 $6$ 天：进行 $10$ 次股票购买。用 $1150$ 日元买入 $10$ 股，现金变为 $35$ 日元。 - 第 $7$ 天：进行 $11$ 次股票卖出。卖出 $11$ 股，获得 $1650$ 日元，现金变为 $1685$ 日元。 此外，无论如何操作，最终所持现金都无法超过 $1685$ 日元，因此答案为 $1685$。 ## 样例解释 2 在本样例中，连续 $6$ 天什么都不做是最优解。此时，最终所持现金为 $1000$ 日元。 ## 样例解释 3 在本样例中，第 $1$ 天买入 $6$ 股，第 $2$ 天卖出 $6$ 股，最终所持现金为 $1216$ 日元，这样最优。 由 ChatGPT 4.1 翻译