There are ~M+1~ points at which we know that we must have Aeroxis active – just before the first battle (essentially "trainer ~0~"), and for each cloud-type trainer ~T_i~. What remains is determining which Pokemon should be used for the battles in between those points (and after the last of them). For each of those unknown intervals, it's optimal to either use Aeroxis or Brinoble for its entire duration – it doesn't make sense to swap at some point in the middle.

Let's iterate over the ~M~ cloud-type trainers while maintaining a running total of the time taken. For each such trainer, we can first of all add ~A~ to the total time. Then, let ~d~ be the number of non-cloud-type trainers between the current trainer and the previous point at which we must have had Aeroxis active. The time required to beat them using only Aeroxis is simply ~A \times d~. On the other hand, the time required to switch to Brinoble, use it to beat those trainers, and then switch back to Aeroxis is ~2S+d \times B~. We should greedily use whichever of those two strategies is faster, and add that value to the total time. Either way, we'll end up with Aeroxis as required.

The remaining interval is the one after the last cloud-type trainer, and the same approach can be applied to it. Let ~d~ be the number of non-cloud-type trainers after trainer ~T_M~. The time required to beat them using only Aeroxis is again ~A \times d~, while the time required to switch to Brinoble and use it to beat those trainers is ~S+d \times B~ (note that we don't need to switch back to Aeroxis after this interval).

The time complexity of this greedy algorithm is ~\mathcal O(M)~.