说明

输入文件: stock.in 输出文件: stock.out 时间限制: 1 Sec 内存限制: 256 MB

题目描述

小明是一名超能力者，他能以 $1$ 分钟为单位预测当天某一只股票的股价。他的预测绝对准确，无论他进行何种买卖操作，股价都绝不会偏离预测结果。

在当天，小明只会买卖这只他能预测股价的股票。每一分钟，他都可以选择买卖该股票，或是观望。

小明当天进行任意多次买入股票的操作，买入股票会以该时间点的股价将手工的资金换成股票；但最多可进行 $ M $ 次卖出股票的操作，卖出股票会以该时间点的股价将每 $1$ 股股票兑换为资金，从而获得手持资金。每次卖出获得的资金可直接投入下一次股票购买。

已知小明初始手持资金为 $ K $、预测的股价数据，以及最多可进行的卖出次数 $ M $，请计算股市收盘时小明手持资金的最大值。

条件如下：

- 股票可按 $1$ 股为单位进行买卖。

- 股市从 $9$ 点开放，最晚至 $15$ 点 $30$ 分收盘，买卖操作以 $1$ 分钟为单位进行。也就是说，股价数据最多有 $391$ 条。

- 买卖手续费为 $0$ 元。

- 股市收盘后，手中剩余的股票无法兑换为资金。即收盘前必须将所有股票卖出，否则未卖出部分无价值。

输入格式

第一行三个整数 $N,M,K$。

接下来的 $N+1$ 行，每行一个整数 $A_1,A_2,\ldots,A_{N+1}$ 表示每一个时刻的股票的价格。

输出格式

一个整数，表示股市收盘时小明手持现金的最大值。

样例

10 3 2000
200
190
180
170
160
150
150
140
130
120
110

2000

样例说明 #1

股价每天都在走低，不做任何交易是最有策略。

10 3 2000
100
110
120
130
140
150
160
170
180
190
200

4000

样例说明 #2

第一分钟买进，最后一分钟卖出，股价翻一倍，手里现金数量是 $4000$。

21 5 3000
150
144
133
130
127
129
138
142
131
131
126
126
133
135
121
115
122
130
124
110
138
134

5052

数据范围

• 对于 20% 的数据，$N = 1$。
• 对于 50% 的数据，$N \leq 60$。
• 对于 100% 的数据，$1 \leq N \leq 390$，$1 \leq M \leq 20$，$1 \leq K \leq 10000$，$100 \leq A_i \leq 300$。