Cho dãy số nguyên ~a_1, a_2, \dots, a_n~.

Cần chọn ~p~ bộ ba chỉ số

~i_1 < j_1 < k_1 < i_2 < j_2 < k_2 < \dots < i_p < j_p < k_p~.

Với mỗi ~t~ từ ~1~ đến ~p~, độ lấp lánh của bộ ba thứ ~t~ là

~\max(a_{i_t}, a_{j_t}, a_{k_t}) - \min(a_{i_t}, a_{j_t}, a_{k_t})~.

Độ lấp lánh của toàn bộ phương án chọn là giá trị lớn nhất trong ~p~ bộ ba trên.

Yêu cầu

Tìm giá trị nhỏ nhất có thể của độ lấp lánh toàn bộ phương án.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~n, p~.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Kết quả

In ra một số nguyên duy nhất là độ lấp lánh nhỏ nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

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

Output

2

Giải thích

Ví dụ 1

Có thể chọn hai bộ ba giá trị ~3, 4, 4~ và ~-7, -6, -5~.

Độ lấp lánh của hai bộ ba lần lượt là ~1~ và ~2~, nên độ lấp lánh của phương án là ~2~.

Không thể đạt giá trị nhỏ hơn.

Ràng buộc và chấm điểm

Ràng buộc

• ~3 \le n \le 500~
• ~1 \le p~
• ~3p \le n~
• ~|a_i| \le 10^9~

Chấm điểm

• Subtask ~1~ ~(40\%):~ ~3p = n~.
• Subtask ~2~ ~(30\%):~ ~p = 1~.
• Subtask ~3~ ~(30\%):~ Không có ràng buộc bổ sung.