$(30$ PTS$.)$ SCheduling Jobs on Supercomputers

You're running a massive physical simulation, which can only be run on a supercomputer. You've got access to two $($identical$)$ supercomputers, but unfortunately you have a fairly low priority on these machines, so you can only get time slots on them when they'd otherwise be idle. You've been given information about how much idle computing power is available on each supercomputer for each of the next $\backslash ($ n $\backslash )$ one$-$hour time slots: you can get $\backslash ($ a$\_\{$i$\}\backslash )$ seconds of computation done on supercomputer $\backslash ($ A $\backslash )$ in the $\backslash ($ i $\backslash )$ th hour if your job is running on $\backslash ($ A $\backslash )$ at that point, or $\backslash ($ b$\_\{$i$\}\backslash )$ seconds of computation if it running on supercomputer $\backslash ($ B $\backslash )$ at that point. During each hour your job can be scheduled on only one of the two supercomputers. You can move your job from one supercomputer to another at any point, but it takes an hour to transfer the accumulated data between supercomputers before your job can begin running on the new supercomputer, so a one$-$hour time slot will be wasted where you make no progress.

So you need to come up with a schedule, where for each one$-$hour time slot your job either runs on super$-$ computer $\backslash ($ A $\backslash ),$ runs on supercomputer $\backslash ($ B $\backslash ),$ or "moves" $($it switches which supercomputer it will use in the next time slot$).$ If your job is running on supercomputer A for the $\backslash (($i$-1)\backslash )$ th hour, then for the $\backslash ($ i $\backslash )$ th hour your only two options are to continue running on A or to "move." The value of a schedule is the total number of seconds of computation that you get done during the $\backslash ($ n $\backslash )$ hours. You want to find a schedule of maximal value. Design an efficient algorithm to find the value of the optimal schedule, given $\backslash ($ a$\_\{1\},$ a$\_\{2\},\backslash$ldots a$\_\{$n$\}\backslash )$ and $\backslash ($ b$\_\{1\},$ b$\_\{2\},\backslash$ldots$,$ b$\_\{$n$\}\backslash ).$