There are n cities on a highway with coordinates x1 , . . . , xn and we aim to build K < n fire stations to cover these cities. Each fire station has to be built in one of the cities, and we hope to minimize the average distance from each city to the closest fire station. Please give an algorithm to compute the optimal way to place these K fire stations. The algorithm should run in O(n^2K) time. Partial credits will be given to algorithms with slightly higher complexity, for instance, a solution with time complexity O(n^3K) will get 15 points