There is a long stretch of an east-west highway that needs cell phone service. Several transmission stations are needed to provide this service. There must be a station at each endpoint of the highway, but there can be up to T transmission stations in total. There are L locations in which to build the transmission stations.
Each transmission station, that is not on an endpoint, needs two transmitters. One to transmit to the station up the road and one to transmit to the station down the road. The stations on the endpoints will only need one transmitter. Each transmitter has a cost that is proportional to the power used by the transmitter. The power necessary for each transmitter is proportional to the square of the distance that it needs to transmit.
It is your task to find out the minimum cost necessary.
There will be several test cases.
Each test case will start with a line with two positive integers, L and T, with 2 < T < L < 100. Then a line will follow with L distinct non-negative integers. Each integer will be a distance from the eastern most endpoint of the highway. The first will be 0, the last will be the distance to the westernmost endpoint of the highway.
For each case output a line giving the case number and the minimum cost necessary.
4 3 0 1 2 3 5 3 0 1 2 3 4 10 5 0 3 8 4 15 22 20 17 26 30
1: 10 2: 16 3: 452