邮局

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一些村庄被建在一条笔直的高速公路边上。我们用一条坐标轴来描述这条高速公路,每一个村庄的坐标都是整数,没有两个村庄坐标相同。两个村庄间的距离,定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局——当然,并不是每一个村庄都必须建立邮局,邮局必须被建在村庄里,因此它的坐标和它所在的村庄坐标相同。每个村庄使用离它最近的那个邮局,建立这些邮局的原则是:所有村庄到到各自所使用的邮局的距离总和最小。

你的任务是编写一个程序,在给定了每个村庄的坐标和将要建立的邮局数之后,按照上述原则,合理地选择这些邮局的位置。

Input

输入的第1行包含两个整数:第一个整数是村庄的数目V(1<=V<=300);第二个整数是将建立的邮局数P(1<=P<=30且P<=V)。

输入的第2行递增顺序列出了V个整数。这V个整数分别表示了各村庄的位置坐标。对于每一个位置坐标X,1<=X<=10000。

Output

输出的第1行是一个整数S,表示你所求出的所有村庄到距离它最近的邮局的距离总和。相应地,第2行按照递增顺序列出了P个整数,分别表示您所求出的每个邮局的建立位置。虽然对于同一个S,可能会有多种邮局建立的方案,但只需输出其中的一种。

Sample Input

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

Sample Output

9
2 7 22 44 50

Hint

Source