자석

크기가 같은 정사각형 칸 $N$개가 1번부터 $N$번까지 일렬로 놓인 실험대가 있다. $i$번 칸에는 에너지 상수 $a_i$가 설정되어 있고, 모든 칸은 외부 배터리와 연결되어 있다.

이하는 실험대에 일자 모양 자석 하나를 설치하려고 한다. 자석의 길이는 2부터 $N$까지 원하는 값으로 정할 수 있다. 자석의 한쪽 끝에는 한 칸 크기의 N극이 있고, 반대쪽 끝에는 한 칸 크기의 S극이 있다. 두 극은 각각 정확히 하나의 칸 위에 놓여야 한다.

자석을 설치하면 배터리의 에너지가 다음 세 가지 현상으로 동시에 변한다.

1. N극이 놓인 칸의 에너지 상수만큼 배터리에 에너지가 충전된다.
2. S극이 놓인 칸의 에너지 상수만큼 배터리의 에너지가 소모된다.
3. N극이 놓인 칸 번호와 S극이 놓인 칸 번호의 차에 $K$를 곱한 만큼 배터리에서 에너지가 소모된다. 두 수의 차는 큰 수에서 작은 수를 뺀 값이다.

이하는 배터리를 최대한 충전하려고 한다. 자석을 놓기 전과 비교했을 때 얻을 수 있는 배터리 에너지 변화의 최댓값을 구하라. 실험 결과 배터리의 에너지가 실험 전보다 줄어들 수도 있다.

첫 번째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 500\,000$, $0 \leq K \leq 2\,000$)

두 번째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. ($0 \leq a_i \leq 10^9$)

첫 번째 줄에 자석을 놓기 전과 비교했을 때 얻을 수 있는 배터리 에너지 변화의 최댓값을 출력한다.

예제 1의 경우 N극을 3번 칸에, S극을 5번 칸에 놓도록 자석을 설치하면 1번 현상으로 $a_3=22$의 에너지가 충전되고, 2번 현상으로 $a_5=4$의 에너지가 소모되며, 3번 현상으로 $(5-3) \times 2=4$의 에너지가 소모된다. 설치 전과 비교하면 총 14의 에너지가 충전된다. 이보다 더 많은 에너지를 충전할 수 있는 방법은 없다.