← 返回题目列表

Codeforces · 385/A

A. 熊和覆盆子

中文机器翻译题面 查看原题

熊决定储存一些覆盆子过冬。他狡猾地找出了接下来 n 天的每一天一桶蜂蜜(以公斤覆盆子为单位)的价格。根据熊的数据,在第 i (1 ≤ i ≤ n) 天,一桶蜂蜜的价格将是 xi 公斤覆盆子。

不幸的是,熊既没有蜂蜜桶,也没有覆盆子。与此同时,熊的一个朋友愿意借给他一桶蜂蜜,为期一天,价格为c公斤覆盆子。这就是为什么熊想出了一个聪明的计划。他想选择某天d(1≤d<n),借出一桶蜂蜜并立即(在d天)按照每日汇率出售。第二天(d+1),熊想按照每日汇率购买一桶新蜂蜜(因为他卖掉前一桶蜂蜜还剩下一些树莓),并立即(在d+1天)把借来的一桶蜂蜜交给他的朋友,并给他的朋友c公斤树莓以租用这桶蜂蜜。

熊最多想执行一次他的计划,然后冬眠。他最多可以获得多少公斤的覆盆子?请注意,如果在计划的某个时刻,熊用完了覆盆子,那么他就不会执行这样的计划。

输入

第一行包含两个空格分隔的整数 n 和 c (2 ≤ n ≤ 100, 0 ≤ c ≤ 100), — 熊借桶时应借出的天数和树莓的公斤数。

第二行包含n个空格分隔的整数x1, x2, ..., xn (0 ≤ xi ≤ 100),即第i天一桶蜂蜜的价格。

输出

打印一个整数——问题的答案。

示例

输入 #1

5 1
5 10 7 3 20

输出 #1

3

输入 #2

6 2
100 1 10 40 10 40

输出 #2

97

输入 #3

3 0
1 2 3

输出 #3

0

注意

在第一个样本中,熊会在第 3 天借出一桶蜂蜜,然后以 7 美元的价格出售。然后熊会以 3 美元的价格购买一桶蜂蜜,并将其归还给朋友。因此,利润为 (7 - 3 - 1) = 3。

在第二个样本中,熊会在第 1 天借出一桶蜂蜜,然后以 100 的价格出售。然后熊在第 2 天以 1 的价格购买该桶。因此,利润为 (100 - 1 - 2) = 97。