Có một làng nằm dọc theo một đường cao tốc. Đường cao tốc được biểu diễn bằng một trục số nguyên và vị trí mỗi làng được xác định bởi một số nguyên duy nhất. Không có hai làng nào ở cùng một vị trí. Khoảng cách giữa hai vị trí bằng giá trị tuyệt đối của hiệu nằm giữa hai toạ độ nguyên của chúng.

Một số bưu cục được xây dựng ở một số làng nhưng không nhất thiết tại mọi làng. Mỗi làng và bưu cục thuộc nó có cùng vị trí. Để xây dựng các bưu cục, vị trí của chúng cần chọn sao cho tổng các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với làng đó là nhỏ nhất.

Yêu cầu: Cho biết các vị trí của các làng và số lượng các bưu cục, hãy tìm tổng nhỏ nhất có thể được của các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với nó và các vị trí tương ứng của các bưu cục.

Input

• Dòng thứ nhất chứa hai số nguyên: số thứ nhất là số làng ~v~ (~1 \le v \le 300~), số thứ hai là số lượng bưu cục ~p~ (~1 \le p \le 30~, ~p \le v~).
• Dòng thứ hai chứa ~v~ số nguyên theo thứ tự tăng dần, ~v~ số nguyên này là các vị trí của ~v~ làng. Với mỗi vị trí ~x~, ~1 \le x \le 10000~.

Output

• Dòng thứ nhất chứa một số nguyên ~s~ là tổng nhỏ nhất có thể được của các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với nó.
• Dòng thứ hai chứa ~p~ số nguyên theo thứ tự tăng dần. Các số nguyên này là các vị trí của các làng tại đó đặt bưu cục. Nếu có nhiều lời giải, chỉ cần đưa ra một.

Sample Input 1

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

Sample Output 1

9
2 7 22 44 50