The town of Bozeman, Montana is being overrun by inter-dimensional alien beings called Destructors . The Bozeman research laboratory has created a Destructor Defense System (DDD) to help protect the town. The DDD continuously watches the inter-dimensional space to perfectly predict all future Destructor attacks. The DDD allows Bozeman to predict that i days from now xi Destructors will invade Bozeman. The DDD has a laser rifle that is able to eliminate Destructors, but the rifle takes a lot of time to charge up to be able to use. Basically, charging the laser rifle for j days will allow it to eliminate dj Destructors.

Ex 1: Suppose (x1, x2, x3, x4) = (1, 10, 10, 1) and (d1, d2, d3, d4) = (1, 2, 4, 8). The best solution is to fire the rifle at times 3, 4 in order to eliminate 5 Destructors.

Given an array holding xi and dj , create a dynamic programming algorithm that eliminates the maximum number of Destructors. Explain the running time of your solution.