TRATIENAN Trả tiền ăn

 Trước kì thi HSG Quốc Gia, các thầy cô tổ chức cho đội tuyển Tin liên hoan tại nhà hàng X để giảm bớt áp lực. Khi tính tiền, ông chủ nhà hàng biết đây là đội tuyển Tin tỉnh Đồng Nai nên rất mừng (ngày xưa ông chủ này cũng học chuyên Tin mà!) và đưa ra một cách tính tiền độc đáo như sau: ông viết lên bảng một một dãy V gồm N số nguyên, các học sinh được quyền xóa đi K số. Trong các số còn lại, gọi X là độ chênh lệch lớn nhất và Y là độ chênh lệch nhỏ nhất. Số tiền phải trả là X + Y. Cụ thể, gọi dãy số sau khi xóa là: a₁, a₂, …, a_N-k thì

·        X = max(|a_i – a_j|), i, j = 1 … n – k, i ≠ j.

·        Y = min(|a_i – a_j|), i, j = 1 … n – k, i ≠ j.

               Ví dụ: nếu chủ nhà hàng cho đội tuyển xóa k = 2 số trong dãy gồm n = 5 số -3 -2 3 8 6.  Học sinh có thể chọn xóa 2 số đầu tiên. Khi đó X = 8 – 3 = 5 và Y = 8 – 6 = 2. Số tiền phải trả là 7. Đây là số tiền ít nhất.

               Yêu cầu: bạn hãy giúp đội tuyển chọn K số để xóa sao cho số tiền phải trả X + Y là ít nhất nhé!

Input:

·        Dòng đầu tiên chứa hai số nguyên dương, N (3 ≤ N ≤ 10⁶) và K (1 ≤ K ≤ N - 2).

·        Dòng thứ hai chứa N số nguyên (-5.10⁶ ≤ a_i ≤ 5.10⁶).

Output: ghi số tiền ít nhất đội tuyển phải trả.

Input	Output
5 2 -3 -2 3 8 6	7

Giới hạn: 75% test có N ≤ 10³.