Bạn điều hành một công ty công nghệ thông tin chuyên sao lưu dữ liệu máy tính cho các văn phòng lớn. Công việc sao lưu không thú vị, nên bạn thiết kế một hệ thống để các văn phòng sao lưu dữ liệu cho nhau, còn bạn có thể ở nhà chơi trò chơi máy tính.

Tất cả các văn phòng nằm dọc theo cùng một con phố. Bạn quyết định ghép các văn phòng thành từng cặp và nối hai tòa nhà trong mỗi cặp bằng một dây cáp mạng để chúng có thể sao lưu dữ liệu cho nhau.

Tuy nhiên, cáp mạng rất đắt. Công ty viễn thông chỉ cung cấp \(k\) dây cáp, nên bạn chỉ có thể thiết lập sao lưu cho đúng \(k\) cặp, gồm tổng cộng \(2k\) văn phòng. Không văn phòng nào được thuộc nhiều hơn một cặp; tức là \(2k\) văn phòng này phải đôi một khác nhau.

Công ty viễn thông tính phí theo số kilômét cáp. Hãy chọn \(k\) cặp sao cho tổng khoảng cách giữa hai văn phòng trong mỗi cặp là nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa hai số nguyên \(n,k\), lần lượt là số văn phòng trên phố và số dây cáp mạng có sẵn.

Mỗi dòng trong \(n\) dòng tiếp theo chứa một số nguyên \(s\), là khoảng cách tính bằng kilômét từ một văn phòng đến đầu phố. Các khoảng cách được cho theo thứ tự tăng dần. Không có hai văn phòng ở cùng một vị trí.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên dương là tổng chiều dài cáp mạng nhỏ nhất cần dùng để nối \(2k\) văn phòng khác nhau thành \(k\) cặp.

Ràng buộc

• \(2 \le n \le 100\,000\).
• \(1 \le k \le \lfloor n/2 \rfloor\).
• \(0 \le s \le 1\,000\,000\,000\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

5 2
1
3
4
6
12

4

Nguồn

APIO 2007 — Backup.