题目描述

一天狗狗开车带着糖果收藏家咖波来到了糖果街，糖果街上有n家相邻的糖果店，其中第i家糖果店的美味度为a~i~。咖波会依次经过这些糖果店，当其选择造访第i家糖果店后咖波会获得等于其美味度a~i~的幸福度，但咖波身为收藏家有很高的追求，如果他事先已经造访过美味度大于或等于该店的糖果店，则咖波会拒绝选择造访该店。

这本来该是简单美好的一天，可惜狗狗的油不够了，他只能送咖波到他选择造访的第一家店，然后去加油再到咖波选择造访的最后一家店接咖波上车。咖波身为一只懒货很讨厌走路，每从一家店移动到相继的下一家店都会损失$k$点幸福度，换句话说每当咖波从第$i$家店到第$i+1$家店时都会损失$k$点幸福度。请你告诉咖波他最终所能获得的最大幸福度。

输入格式

第一行两个整数 $n$和$k$。

第二行 $n$ 个整数$a_{i}$。

$1\\leq n\\leq 10^5$，$1\\leq k\\leq 10^5$,$1\\leq a_i\\leq 10^5$。

输出格式

输出共一行

一个整数，代表咖波最终能获得最大幸福度。

样例

7 2 
1 7 8 8 8 9 1

16

5 100 
1 2 3 4 5

5

提示

样例一中咖波选择了造访第2、3、6家糖果店，糖果店能带来7+8+9=24点幸福度。狗狗会在第2家糖果店放咖波下车，然后在第6家店接咖波上车，所以咖波会因为移动失去8点幸福度，可知没有其他方案能大于16故答案为16。