Mô tả và yêu cầu

Lớp học nhảy
Một lớp học nhảy có 𝑛 học viên, học viên thứ 𝑖 có chiều cao là ℎ𝑖 (𝑖 = 1,2, … ,𝑛). Trong một buổi
học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra 𝑘 đôi nhảy, mỗi đôi gồm
hai học viên để trình diễn và rút kinh nghiệm. Với một đôi nhảy, chênh lệch chiều cao giữa hai
học viên càng nhỏ càng tốt, do đó, thầy giáo muốn lựa chọn ra 𝑘 đôi nhảy mà tổng các chênh lệch
chiều cao giữa hai học viên trong cùng một đôi của cả 𝑘 đôi là nhỏ nhất.
Yêu cầu: Cho 𝑛 số nguyên dương ℎ1, ℎ2, … ,ℎ𝑛 là chiều cao của 𝑛 học viên và số nguyên dương
𝑘, hãy chọn ra 𝑘 đôi nhảy mà tổng các chênh lệch chiều cao giữa hai học viên trong cùng một đôi
của cả 𝑘 đôi là nhỏ nhất.
Dữ liệu: Vào từ file văn bản DANCE.INP:
- Dòng đầu chứa hai số nguyên dương 𝑛, 𝑘 (𝑘 ≤ ⌊𝑛⌋, trong đó ⌊𝑛⌋ là số nguyên lớn nhất
𝑛 2 2
không vượt quá 2);
- Tiếp theo là một dòng chứa 𝑛 số nguyên dương ℎ1, ℎ2, … ,ℎ𝑛 (ℎ𝑖 ≤ 109).
Kết quả: Ghi ra file văn bản DANCE.OUT một số là số tổng các chênh lệch chiều cao giữa hai
học viên trong cùng một đôi của cả 𝑘 đôi là nhỏ nhất.

Giới hạn và chấm điểm

 Có 40% số lượng test ứng với 40% số điểm của bài thỏa mãn: 𝑛 ≤ 10;
 Có 30% số lượng test khác ứng với 30% số điểm của bài thỏa mãn: 𝑛 ≤ 1000; 𝑘 = ⌊𝑛⌋;
2
 Có 30% số lượng test còn lại ứng với 30% số điểm của bài thỏa mãn: 𝑛 ≤ 1000.

Ví dụ

DANCE.INP                           DANCE.OUT
                      5 2                                 1
                      2 5 3 3 6