Ô tô bay

Hãng ô tô BN đang trong giai đoạn thử nghiệm một mẫu ô tô bay đời mới. Trong quá trình vận hành, khi gặp một chướng ngại vật có độ cao \(h\), chiếc xe phải ``nâng'' độ cao của nó lên mức \(l \ge h\) để vượt qua. Tuy nhiên, việc bay càng cao so với chướng ngại vật sẽ càng tiêu tốn nhiều năng lượng, vì vậy hãng quy ước độ lãng phí khi ô tô bay ở độ cao \(l\) và vượt chướng ngại vật độ cao \(h\) là \(l - h\).

Trong bài thử nghiệm, có \(n\) chướng ngại vật đánh số từ \(1\) đến \(n\) có độ cao lần lượt là \(h_1, h_2, \ldots, h_n\) được xếp liên tiếp từ trái sang phải theo thứ tự từ \(1\) đến \(n\) trên một đường thẳng. Ô tô cần bay từ bên trái chướng ngại vật \(1\) qua bên phải chướng ngại vật \(n\). Do đây vẫn là phiên bản thử nghiệm nên trong suốt quá trình thử nghiệm, ô tô chỉ được phép nâng độ cao của nó lên tối đa một lần và không được hạ độ cao. Khi xuất phát, ô tô được nâng lên độ cao bất kỳ và lần nâng này không tính vào lần nâng trong quá trình thử nghiệm.

Yêu cầu: Tìm tổng độ lãng phí nhỏ nhất để ô tô hoàn thành bài thử nghiệm như mô tả ở trên.

Input

Dữ liệu vào gồm:

• Dòng 1: Gồm \(2\) số nguyên \(n, k\) (\(-1 \le k \le 1\), \(1 \le n \le 10^6\)), trong đó \(n\) là số chướng ngại vật, số \(k\) có ý nghĩa như sau:

  • Nếu \(k = 0\): Ô tô không được nâng độ cao lần nào nhưng độ cao xuất phát ban đầu tùy ý.

• Nếu \(k = -1\): Ô tô được nâng độ cao tối đa một lần và xe phải xuất phát ở độ cao bằng \(h_1\).

• Nếu \(k = 1\): Ô tô được nâng độ cao tối đa một lần và được chọn độ cao xuất phát ban đầu tùy ý.

• Dòng 2: Gồm \(n\) số nguyên \(h_1, h_2, \ldots, h_n\) (\(0 \le h_i \le 10^9\) với mọi \(i = 1 \ldots n\)) là độ cao của các chướng ngại vật.

Ràng buộc:

• Có \(40\%\) số điểm có: \(k = 0\) và \(n \le 10^6\);

• Có \(30\%\) số điểm tiếp có: \(k = -1\) và \(n \le 10^6\);

• \(30\%\) số điểm còn lại có: \(k = 1\) và \(n \le 10^4\).

Output

In ra một số nguyên là tổng độ lãng phí nhỏ nhất tìm được theo yêu cầu.

Example 1

Input:

5 0
7 9 2 5 8

Output:

14

Example 2

Input:

6 -1
5 4 6 8 3 6

Output:

10

Example 3

Input:

7 1
5 4 6 8 9 3 7

Output:

12

Note

Giải thích ví dụ 3: Xe xuất phát với độ cao bằng \(6\) và giữ độ cao này bay qua các chướng ngại vật thứ \(1, 2, 3\). Khi gặp chướng ngại vật thứ \(4\) xe nâng độ cao lên bằng \(9\) rồi giữ độ cao này bay về đích.

Tổng độ lãng phí là: \((6-5)+(6-4)+(6-6)+(9-8)+(9-9)+(9-3)+(9-7) = 12\).