$(25$ points$)$ A factory manufactures custom widgets, each requiring a specific assembly time

and a painting time. The factory has multiple workers available for painting, but only one

assembly line, which can handle one widget at a time. Each widget $W_i$ needs $A_i$ minutes

for assembly and $P_i$ minutes for painting. The painting of a widget can only begin after it

has been assembled, but multiple widgets can be painted in parallel. Write an algorithm

that, given a set of $n$ widgets, determines a schedule $W_{i_1},W_{i_2},$cdots,$W_{i_n}$ that such that all the

widgets are completely finished in the shortest overall time. Derive the runtime and prove

the correctness of your algorithm formally.