股票市场(Stock Market)

题目描述

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

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

输入格式

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

输出格式

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

样例输入 #1

3 10 1 2 3

样例输出 #1

30

样例输入 #2

4 100 40 20 10 5

样例输出 #2

100

样例输入 #3

6 100 1 2 10 1 5 10

样例输出 #3

10000

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布