등산 경로 Batch 컴파일 명령

부자인 석환이는 등산을 위해 산에 길을 만들었습니다. 이 경로는 출발지와 도착지가 같습니다. (순환 경로) 우리는 이 길을 폭이 일정한 계단이라고 생각해 보겠습니다. $i$번째 계단은 지면에 수직하며 해발 고도 $a_{i}$m에 위치했다고 생각할 수 있습니다. 이웃한 계단의 높이가 일정할 수도 있습니다. 이 때 경로의 난이도는 오르락내리락하는 높이의 합입니다. 더 정확히 표현하면,

• 난이도 = $|a_{1} - a_{2}| + |a_{2} - a_{3}| + \cdots + |a_{n-1} - a_{n}| + |a_{n} - a_{1}|$

석환이가 첫 번째로 건설한 등산로는 등산객들이 너무 어려워했기 때문에, 석환이는 $k$개의 벽돌을 사용해서 난이도를 줄이고자 합니다. 벽돌의 폭은 계단의 폭과 같으며, 높이는 1m입니다. 우리는 모든 계단에 벽돌을 올려놓을 수 있으며, 벽돌 위에 벽돌을 올릴 수도 있고, 벽돌을 아예 사용하지 않을 수도 있습니다.

석환이는 난이도를 가능한 한 많이 줄이려고 합니다. $k$개의 벽돌을 적절히 배치해서 난이도의 감소량의 최댓값이 얼마나 되는지 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에는 $n$ ($2 \le n \le 10^{6}$)과 $k$ ($1 \le k \le 10^{9}$)가 공백을 사이로 두고 주어집니다. 다음 줄에는 각 계단의 높이를 나타내는 $n$개의 $0$이상의 정수가 주어집니다.

출력 형식

첫 번째 줄에 난이도의 감소량의 최댓값을 출력합니다.

예제

예제 1

입력

4 5
4 3 2 1

출력

4

예제 2

입력

3 2
1 2 1

출력

2

예제 3

입력

7 1000
4 3 3 2 3 2 1

출력

8

참고

첫 번째 예제에서 초기 상태의 난이도는 6입니다. (1만큼 세 번 내려가고, 마지막에 3만큼 올라갑니다.) 벽돌 하나를 세 번째 계단에 놓고 벽돌 두 개를 네 번째 계단에 놓으면, 계단의 높이는 "4 3 3 3"이 되어 난이도가 4만큼 감소했습니다. 벽돌 5개를 사용해도 같은 결과를 낼 수 있으나 난이도를 더 이상 줄일 수는 없습니다.

30%의 데이터에 대해 $N \le 100, k \le 1000.$

60%의 데이터에 대해 $N \le 100000.$