THIS QUESTION MUST BE ANSWERED WITH CLEAR ENGLISH PSEUDOCODE!

At a certain theme park there are n rides, numbered from 1 to n. Before you can go on ride i you must pay its cost C[i] dollars, plus a deposit, D[i] dollars. This means you must have at least C[i] + D[i] dollars to go on the ride. Once you have finished the ride, D[i] dollars are returned to you, as long as you did not damage the ride! Careful Cheryl never damages any rides, and currently has T dollars on her. Cheryl woulod like to know the maximum number of different rides she can go on. She can go on rides iin any order she chooses. You may assume C[1..n] and D[1..n] are both positive integer arrays of length rn (a) Prove that, if an amount of money T is enough for Cheryl to go on some subset S of all the rides in some order, then she can go on the same subset S of rides in a non-increasing order of deposit D[i] (breaking ties arbitrarily). (b) Hence, design an O(n log n+ nT ) algorithm to determine the maximum number of different rides Cheryl can go on (c) Does an O(n log n + nT) algorithm for this problem run in polynomial time? Why or why not? (d) Design an algorithm for the same task, but which runs in time O(n2) At a certain theme park there are n rides, numbered from 1 to n. Before you can go on ride i you must pay its cost C[i] dollars, plus a deposit, D[i] dollars. This means you must have at least C[i] + D[i] dollars to go on the ride. Once you have finished the ride, D[i] dollars are returned to you, as long as you did not damage the ride! Careful Cheryl never damages any rides, and currently has T dollars on her. Cheryl woulod like to know the maximum number of different rides she can go on. She can go on rides iin any order she chooses. You may assume C[1..n] and D[1..n] are both positive integer arrays of length rn (a) Prove that, if an amount of money T is enough for Cheryl to go on some subset S of all the rides in some order, then she can go on the same subset S of rides in a non-increasing order of deposit D[i] (breaking ties arbitrarily). (b) Hence, design an O(n log n+ nT ) algorithm to determine the maximum number of different rides Cheryl can go on (c) Does an O(n log n + nT) algorithm for this problem run in polynomial time? Why or why not? (d) Design an algorithm for the same task, but which runs in time O(n2)