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 \le 3 \times p \le n)~.

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

Output

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

Scoring

Sample Input 1

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

Sample Output 1

2