Let A=a1, a2, ..., an be a set of n distinct records in which record ai is associated with an integer weight wi>0 and wi's are distinct. Let W=sum(wi). The weighted selection problem is to identify the smallest record ai of A so that sum(wj) < W/4 for all aj < ai and sum(wj) >= W/4 for all aj <= ai. Describe and analyze an efficient algorithm to solve the weighted selection problem. Note that an O(n logn)-time algorithm is straight forward by using sorting, say merge-sort, so we are looking for a better algorithm.