In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
After a new administrative division of Byteland cartographic office works on a new demographic map of the country. Because of technical reasons only a few colors can be used. The map should be colored so that regions with the same or similar population (number of inhabitants) have the same color. For a given color let be the number, such that:
A coloring error of a region marked with color is an absolute value of the difference between and the region's population. A cumulative error is a sum of coloring errors of all regions. We are looking for an optimal coloring of the map (the one with the minimal cumulative error).
Write a program which:
In the first line of the standard input an integer is written, which is the number of regions in Byteland, . In the second line the number denoting the number of colors used to color the map is written, . In each of the following lines there is one non-negative integer - a population of one of the regions of Byteland. No population exceeds .
Your program should write in the only line of the standard output one integer number equal to a minimal cumulative error, which can be achieved while the map is colored (optimally).
For the input data:
11 3 21 14 6 18 10 2 15 12 3 2 2
the correct result is:
Task author: Marcin Sawicki.