공매도

Simone은 암호화폐 거래를 배우고 있다. 지금 살펴보고 있는 것은 CryptoKattis라는 새 화폐다. CryptoKattis를 쓰면 문제를 풀지 않고도 Kattis 랭킹 점수를 올릴 수 있다.

대부분의 경쟁 프로그래머와 달리 Simone은 대회 흐름을 잘 읽는다. 최근 많은 코더가 Doggo라는 새 온라인 저지를 이야기하는 것을 보고, Kattis 저지를 쓰는 것이 곧 유행에서 밀려나리라 짐작했다. 그러면 수요가 사라지면서 CryptoKattis의 가치도 빠르게 떨어질 것이다.

Simone은 이를 이용하려고 시장 조사를 꼼꼼히 했다. 덕분에 앞으로 $N$일 동안 CryptoKattis 한 개의 가격을 달러 단위로 추정할 수 있다. 이 데이터로 공매도를 하려 한다. 어떤 날에 은행에서 CryptoKattis $100$개를 빌려 곧바로 팔고, 다른 날에 같은 수의 CryptoKattis를 사서 빌린 것을 갚는다. 이 두 날 사이의 모든 날(양 끝 날 포함)에 대해 하루에 $K$달러의 이자를 내야 한다. CryptoKattis $100$개를 빌리고 갚는 날을 잘 골라서 Simone이 얻을 수 있는 최대 이익은 얼마인가?

첫째 줄에 두 정수 $1 \le N \le 100\,000$과 $1 \le K \le 100$이 주어진다. $N$은 CryptoKattis 가격을 아는 날의 수이고, $K$는 CryptoKattis를 빌리는 데 하루에 드는 비용(달러)이다.

다음 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. 이는 $N$일 동안의 CryptoKattis 가격이다. 각 CryptoKattis 가격은 $1$달러와 $100\,000$달러 사이이다.

공매도로 얻을 수 있는 최대 이익을 소수 하나로 출력한다. 어떤 공매도를 해도 이익을 낼 수 없다면 $0$을 출력한다.