Các ngôi làng nằm dọc theo một đường quốc lộ thẳng, được biểu diễn bằng một trục tọa độ nguyên. Mỗi làng có một tọa độ nguyên riêng; không có hai làng ở cùng vị trí. Khoảng cách giữa hai vị trí bằng giá trị tuyệt đối của hiệu hai tọa độ.

Người ta sẽ xây bưu điện tại một số làng, không nhất thiết ở tất cả các làng. Một bưu điện có cùng tọa độ với làng nơi nó được xây. Cần chọn vị trí các bưu điện sao cho tổng khoảng cách từ mỗi làng đến bưu điện gần nhất là nhỏ nhất.

Cho tọa độ các làng và số bưu điện cần xây, hãy tìm tổng khoảng cách nhỏ nhất có thể và các vị trí xây bưu điện tương ứng.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(V\), \(P\): số làng và số bưu điện, với \(1 \le V \le 300\), \(1 \le P \le 30\) và \(P \le V\). Dòng thứ hai chứa \(V\) số nguyên theo thứ tự tăng dần, là tọa độ các làng. Mỗi tọa độ \(X\) thỏa mãn \(1 \le X \le 10000\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(S\), là tổng khoảng cách từ mỗi làng đến bưu điện gần nhất trong phương án được in ở dòng thứ hai. Dòng thứ hai chứa \(P\) số nguyên theo thứ tự tăng dần, là tọa độ của \(P\) làng khác nhau nơi xây bưu điện. Nếu có nhiều phương án tối ưu, chỉ cần in một phương án.

Chấm điểm

Nếu kết quả không thỏa mãn các yêu cầu về dữ liệu ra, điểm là \(0\). Ngược lại, gọi \(S_{\min}\) là tổng khoảng cách nhỏ nhất thực sự. Nếu \(S=S_{\min}=0\), kết quả được điểm tối đa, tức là \(c=10\). Khi \(S_{\min}>0\), đặt \(q=S/S_{\min}\); điểm \(c\) của lần chạy được xác định theo bảng sau:

Ví dụ

10 5
1 2 3 6 7 9 11 22 44 50

9
2 7 22 44 50