Cho dãy số nguyên ~a_1, a_2, \ldots, a_n~ và số nguyên dương ~k~. Thực hiện phép xóa ~k~ phần tử sao cho chênh lệch nhỏ nhất giữa ~2~ phần tử bất kỳ còn lại là lớn nhất. Gọi ~W~ là độ chênh lệch cần tìm.

Yêu cầu

Tìm cách xóa để ~W~ nhận giá trị lớn nhất.

Input

Đọc từ tệp MAXDIF.INP:

• Dòng đầu chứa hai số nguyên dương ~n, k~ (~k \le n - 2~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~).

Output

Ghi vào tệp MAXDIF.OUT một số nguyên là giá trị ~W~ lớn nhất tìm được.

Ví dụ

Input

5 1
4 1 2 3 9

Output

1

Giới hạn

• Có 20% số test của bài thỏa mãn ~n \le 20~.
• Có 30% số test của bài thỏa mãn ~20 < n \le 100~.
• Có 25% số test tiếp theo của bài thỏa mãn ~100 < n \le 2000~.
• Có 25% số test còn lại của bài thỏa mãn ~2000 < n \le 10^5~.