Enemy missiles are arriving over the course of n seconds; in the i-the second, xi missiles arrive. Based on remote sensing data, you know the sequence x1, x2, . . . , xn in advance. You are in charge of an electromag- netic pulse (EMP), which can destroy some of the missiles as they arrive. The power of EMP depends on how long it has been allowed to charge up. More precisely, there is a function f so that if j seconds have passed since the EMP was last used, then it is capable of destroying up to f(j) missiles. So, if the EMP is being used in the k-th second and it has been j seconds since it was previously used, then it destroys min{xk, f(j)} missiles in the k-th second. After this use, it will be completely drained. We assume that the EMP starts off completely drained, so if it used for the first time in the j-th second, then it is capable of destroying up to f(j) missiles. Your goal is to choose the points in time at which the EMP is going to activated so as to destroy as many as missiles as possible. Give an efficient algorithm that takes the data on missile arrivals x1, . . . , xn, and the recharging function f, and returns the maximum number of missiles that can be destroyed by a sequence of EMP activations. Analyze the running time of your algorithm.