Xóa số

Cho dãy \(A\) gồm \(N\) phần tử nguyên \(A_1, A_2, \ldots, A_N\) và số nguyên dương \(K\). Khi thực hiện thao tác xóa \(K\) phần tử bất kì khỏi dãy \(A\) ta thu được dãy \(B\) gồm các phần tử còn lại của dãy \(A\). Gọi \(M\) là hiệu lớn nhất giữa hai số bất kỳ trong dãy \(B\), \(m\) là hiệu không âm nhỏ nhất giữa hai số bất kỳ trong dãy \(B\).

Yêu cầu: Tìm giá trị nhỏ nhất của \(|M| + |m|\).

Input

Dữ liệu vào gồm hai dòng:

• Dòng 1: Ghi hai số nguyên dương \(N\) và \(K\) (\(3 \le N \le 10^6\), \(1 \le K \le N - 2\));

• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(|A_i| \le 5 \times 10^6\); \(i = 1, 2, \ldots, N\)).

Ràng buộc:

• Subtask 1: Có \(30\%\) số test ứng với \(30\%\) số điểm có \(N \le 20\);

• Subtask 2: Có \(40\%\) số test ứng với \(40\%\) số điểm có \(N \le 10^3\);

• Subtask 3: Có \(30\%\) số test ứng với \(30\%\) số điểm có \(N \le 10^6\).

Output

In ra một giá trị duy nhất là kết quả của bài toán.

Example 1

Input:

5 2
-3 -2 3 8 6

Output:

7

Example 2

Input:

6 2
-5 8 10 1 13 -1

Output:

13

Note

Ví dụ 1: Có thể xóa hai số \(-3, -2\). Dãy \(B = (3, 8, 6)\), \(M = 5\); \(m = 2\), kết quả bằng \(5 + 2 = 7\).

Ví dụ 2: Có thể xóa hai số \(-5, 13\). Dãy \(B = (8, 10, 1, -1)\), \(M = 11\); \(m = 2\), kết quả bằng \(11 + 2 = 13\).