Bạn là người được giao nhiệm vụ sao lưu giữ liệu cho văn phòng của công ty. Các văn phòng nằm trên một đường thẳng số thực và được đánh số từ tới , văn phòng thứ ở vị trí , không có hai văn phòng nằm ở cùng một vị trí.
Bạn được phép nối cáp giữa hai văn phòng để dữ liệu của chúng được sao chép sang nhau. Bạn chỉ được phép dùng cáp nối để nối đúng cặp văn phòng và mỗi văn phòng chỉ được phép có tối đa một cáp nối với nó. (Tổng cộng phải có đúng văn phòng được sao lưu dữ liệu theo cách này, những văn phòng còn lại bạn sẽ phải tự mang đĩa đến để sao lưu).
Vấn đề là chi phí nối cáp khá đắt, bạn cần tìm cách nối sao cho tổng độ dài cáp nối là ít nhất.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương ;
Dòng thứ hai chứa số nguyên không âm .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là tổng độ dài cáp nối theo phương án tìm được.
Ví dụ:
Dữ liệu vào:
5 2
1 3 4 6 12
Dữ liệu ra:
4
Giải thích:
Phương án tối ưu là nối văn phòng với văn phòng bằng cáp độ dài , nối văn phòng với văn phòng cũng bằng cáp độ dài .
