4. 125 points] CLRS 9.3-9 Collaborative Problem: Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route either north or south), as shown in Figure 9.2 in the textbook. Given the r- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal location in linear time, and prove the correctness and linear bound of the algorithm