Cho một dãy gồm $N$ số tự nhiên $a_1,a_2,a_3...a_n$ $(3\le N\le {10}^6;|a_i|\le {10}^6,1\le i\le N)$

Xóa $K$ số bất kỳ từ dãy số $a_1,a_2,a_3...a_n$ $(1\le K\le N-2)$. Sau khi xóa, gọi $max$ là chênh lệch lớn nhất giữa hai số bất kỳ trong dãy số.

Yêu cầu: Tìm cách xóa $K$ phần tử sao cho $max$ là nhỏ nhất

Dữ liệu vào:

• Dòng 1: Hai số tự nhiên $N$ và $K$
• Dòng 2: $N$ số tự nhiên $a_1,a_2,a_3...a_n$

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả $max$ tìm được.

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm $K\le 2$
• Có 40% số test tương ứng 40% số điểm $2\le K\le 4$
• Có 20% số test còn lại không có ràng buộc gì thêm

Input 1

5 1
1 2 6 8 10

Output 1

7

Input 2

5 2
1 2 6 8 10

Output 2

4