IOI '00 - Beijing, China

Post Office

There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.

Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.

You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office, and the respective desired positions of the post offices.

Input

The first line contains two integers: the number of villages V (1 ≤ V ≤ 300) and the number of post offices P (1 ≤ P ≤ 30, P ≤ V). The second line contains V integers in increasing order. These V integers are the positions of the villages. Each is between 1 and 10 000, inclusive.

Output

The first line should contain one integer S: the sum of all distances between each village and its nearest post office as reported in the second line. The second line contains P integers in increasing order. These integers are the locations of the distinct villages in which the post offices will be built. There may be several different solutions for the locations, and your program needs to output only one of them.

Sample Input

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

Sample Output

9
2 7 22 44 50

Scoring

If your program's output does not satisfy the output requirements, then your score is zero. Otherwise, your score will be computed based on Table 1 as follows. If your program outputs sum S and the actual least possible sum is S_min, then calculuate q = S/S_min and find your score c in the bottom row as a fraction of the maximum possible score on that test case.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 22, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...