The wildly popular Spanish$-$language search engine El Goog needs to do a serious amount of computation every time it recompile its index. Fortunately, the company has at its disposal a single large supercomputer, together with an essentially unlimited supply of high$-$end PCs$.$They$$ve broken the overall computation into n distinct jobs, labeled J$1,$ J$2,...,$ Jn $,$ which can be performed completely independently of one another. Each job consists of two stages: first it

needs to be pre$-$processed on the supercomputer, and then it needs to be finished on one of the PCs$.$ Let$$s say that job Ji needs pi seconds of time on the supercomputer, followed by fi seconds of time on a PC$.$Since there are at least n PCs available on the premises, the finishing of the jobs can be

performed fully in parallel$$all the jobs can be processed at the same time. However, the super$-$computer can only work on a single job at a time, so the system managers need to work out an order in which to feed the jobs to the supercomputer. As soon as the first job in order is done on the supercomputer, it can be handed off to a PC for finishing; at that point in time a second

job can be fed to the supercomputer; when the second job is done on the supercomputer, it can proceed to a PC regardless of whether or not the first job is done $($since the PCs work in parallel$)$;

and so on$.$Let$$s say that a schedule is an ordering of the jobs for the supercomputer, and the completion time of the schedule is the earliest time at which all jobs will have finished processing on the PCs$.$This is an important quantity to minimize, since it determines how rapidly El Goog can generate a new index.

Give a polynomial$-$time algorithm that finds a schedule with as small a completion time as possible. You should also prove that your algorithm results in an optimal solution, and it needs to be a formal proof.