Please describe algorithm, give pseudocode, argue correctness and given best upper bound running time.

5. (30 points) There are n libraries L1, L2, ..., Ln. We want to store copies of a book in some libraries. Storing a copy at Li incurs a purchase cost Gi (assume integer (i > 0). A copy of the book is always stored at Ln. If a user requests the book from Li and Li does not have it, then Lil1, Li 12, ... are searched sequentially until a copy of the book is found at L; for some j>i. This results in a user delay of j - i. (Note that, in this case, no library Lk with an index k smaller than i is searched; also, if the user finds the book at L, then the user delay is 0.) We define the total cost as the sum of the purchase costs and the user delays associated with all n servers. For example, if there are 4 libraries, and copies of the book are stored at Li and L4, the total cost is c +64 +2+1. Give an efficient algorithm that returns (a) the minimum total cost; and (b) a set of libraries where copies of the books must be placed to achieve the minimum total cost. 5. (30 points) There are n libraries L1, L2, ..., Ln. We want to store copies of a book in some libraries. Storing a copy at Li incurs a purchase cost Gi (assume integer (i > 0). A copy of the book is always stored at Ln. If a user requests the book from Li and Li does not have it, then Lil1, Li 12, ... are searched sequentially until a copy of the book is found at L; for some j>i. This results in a user delay of j - i. (Note that, in this case, no library Lk with an index k smaller than i is searched; also, if the user finds the book at L, then the user delay is 0.) We define the total cost as the sum of the purchase costs and the user delays associated with all n servers. For example, if there are 4 libraries, and copies of the book are stored at Li and L4, the total cost is c +64 +2+1. Give an efficient algorithm that returns (a) the minimum total cost; and (b) a set of libraries where copies of the books must be placed to achieve the minimum total cost