古董搜寻

题目描述

在一座充满历史气息的古城里，你是一名专门搜寻古代瓷器的收藏家。每天在古玩市场上，某种特定年代的“青花瓷”价格都会有所波动。

已知未来 $n$ 天内，每天该青花瓷的价格为 $a_i$。你手中最多只能同时持有一件青花瓷。你可以在任何一天买入，也可以在任何一天卖出。

但是，古玩公会对每一笔成功的卖出交易都会收取固定的手续费，金额为 $f$。这意味着，如果你在某天以价格 $a_i$ 卖出，你实际获得的利润需要减去这个手续费。买入是不收取费用的。

你的目标是计算在 $n$ 天结束时，你通过买卖青花瓷最多能获得多少纯利润？

输入格式

第一行包含两个整数 $n$ 和 $f$，分别表示总天数和每笔交易的手续费。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天该青花瓷的价格。

输出格式

输出一个整数，表示能获得的最大纯利润。

输入输出样例 #1

输入 #1

6 2
1 3 2 8 4 9

输出 #1

8

输入输出样例 #2

输入 #2

6 3
1 3 7 5 10 3

输出 #2

6

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$，$0 \le f \le 100$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le f \le 10^9$，$0 \le a_i \le 10^9$。