Trong tiết học Mỹ thuật, Zin được cô giáo giao cho bài tập phối màu cho các đỉnh của ~p~ hình tam giác như sau: Zin được cung cấp ~n~ hình tròn được đánh số lần lượt từ 1 đến ~n~.

Hình tròn thứ ~i~ có màu sắc được mã hóa thành một số nguyên ~a_i~.

Đầu tiên Zin chọn ra 3 hình tròn để dán lên 3 đỉnh của tam giác thứ nhất, giả sử chọn các hình tròn có số thứ tự ~i, j, k~ (~i < j < k~) khi đó độ tương phản của tam giác thứ nhất bằng ~\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)~.

Sau đó, Zin chọn 3 hình tròn tiếp theo (từ hình tròn có số thứ tự lớn hơn ~k~) để trang trí cho tam giác thứ 2.

Lặp đi lặp lại các thao tác trên cho đến khi trang trí đủ ~p~ hình tam giác. Độ tương phản của ~p~ hình tam giác là độ tương phản của hình tam giác có độ tương phản lớn nhất.

Yêu cầu: Hãy giúp Zin trang trí cho ~p~ hình tam giác để có độ tương phản là nhỏ nhất có thể.

Input

• Dòng 1: Chứa hai số nguyên ~n, p~ (~3 \le n \le 500~; ~3 \times p \le n~);
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~; ~1 \le i \le n~).

Output

Ghi ra một số nguyên duy nhất là độ tương phản nhỏ nhất có thể tìm được.

Sample Input 1

10 2
3 9 4 4 -7 13 -6 4 -5 1

Sample Output 1

2

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có ~3 \times p = n~;
• Có 30% số test ứng với 30% số điểm của bài có ~p = 1~;
• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.