Cho dãy \(a\) gồm \(n\) phần tử được đánh số thứ tự từ \(1\) đến \(n\). Giá trị của phần tử thứ \(i\) là \(a_i\).

Một cách chọn các cặp phần tử không giao nhau là một cách chọn các cặp sao cho không có phần tử nào thuộc nhiều hơn một cặp.

Yêu cầu: Bạn cần tìm ra cách chọn ra \(k\) cặp phần tử không giao nhau sao cho tổng chênh lệch của giá trị hai phần tử trong một cặp là bé nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) — số lượng phần tử của dãy \(a\) và số lượng cặp cần phải chọn (\(2 \cdot k \leq n \leq 10^5\)).
• Dòng thứ hai chứa giá trị của các phần tử trong dãy \(a\): \(a_1, a_2, \dots, a_n\) (\(1 \leq a_1, a_2, \dots, a_n \leq 10^9\)).

Output

• Gồm một dòng duy nhất chứa kết quả bài toán: tổng chênh lệch giá trị bé nhất của \(k\) cặp phần tử.

Example

5 2
1 2 3 4 5

2

5 1
1 3 5 7 9

2

Scoring

• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \leq 100\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \leq 1000\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(a_1, a_2, \dots, a_n \leq 100\).
• \(10\%\) số điểm còn lại của bài không có ràng buộc gì thêm.