题目描述

小爱知道一只股票在今后 $n$ 天的价格。在第一天开始前，小爱有 $m$ 元，那么在最后一天结束后，她最多能有多少钱呢？小爱每天都可以买入或卖出股票，注意股票在交易时的最小单位为 $1$ 股。例如当有 $13$ 元的时候，若股价为 $4$ 元一股，则最多只能买 $3$ 股。

规定每天只能交易一次，如果当天已经买入股票，就不能卖出，反之，如果当天已经卖出，则不能再买进股票。

输入格式

第一行：两个整数，表示 $n$ 和 $m$； 第二行：$n$ 个整数 $a_1,\dots, a_n$，表示每天的股票价格。

输出格式

单个整数：表示能获得的最大钱数。

3 10
1 2 3

30

样例解释 1

第一天以1元的价格买进10股，到了最后一天以3元的价格卖出，10元变成了30元

4 100
40 20 10 5

100

样例解释 2

没有买股票

6 100
1 2 10 1 5 10

10000

数据范围

• $1 \leq m \leq 100$；
• $1 \leq a_i \leq 100$；
• 对于 $30\%$ 的数据，$1 \leq n \leq 20$；
• 对于 $60\%$ 的数据，$1 \leq n \leq 5,000$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 100,000$；
• 保证输出答案不超过 $10^{18}$。