Input: n nonnegative numbers a1 a2 . an representing the locations of the people, m nonnegative numbers p1 p2 .

Input: n nonnegative numbers a1 ≤ a2 ≤ ... ≤ an representing the locations of the people, m nonnegative numbers p1 ≤ p2 ≤ . . . ≤ pm representing the possible locations of the hospitals, and an integer1≤k≤m. Weassumethatm≤n.

Output: The minimum total distance to the people. Suppose S = {l1,...,lk} ⊆ {1,...,m} is a subset of k hospitals. We assume that every person will go to the nearest hospital, and so we define dist(i,S) = minj∈S |ai −pj| for person i. The objective is to choose a subset S of k hospitals so as to minimize the total distance defined as