We start by considering the case where ~T=1~. In this situation, it is clearly optimal to order the poutine with the highest ~a_i~ value.

Consider a situation where ~T > 1~. Is it ever optimal to ignore the poutine with the highest ~a_i~ value and choose some other types? We claim the answer is no, and we use a proof by contradiction here. Note that ordering a poutine more than once does not increase the utility that it provides. Consider some optimal selection order of poutine that does not include the poutine with the highest ~a_i~ value at all. Note that no order of poutine can provide utility strictly larger than ~a_i~ as a result, but this means we can arbitrarily substitute some chosen poutine with the one that has the highest ~a_i~ value. This does not decrease the utility gained (and in fact may increase it). This implies that we should always select the poutine with the highest ~a_i~ value at every step.

This directly gives an ~\Omega(T)~ algorithm, of the following form:

Repeat the following T times
    Find the poutine that gives the maximum utility now, and order it

However, ~T~ can be as large as ~10^{18}~, so this algorithm will be too slow. Therefore, we have to do better than simulate this process one step at a time.

If we look at the structure more carefully here, we note that the utility values that we gain at each time step are nonincreasing. Because of this, we can perform a binary search on the utility that Thomas will gain on the ~T~th iteration of this algorithm. Let this value be ~v~. Thomas will look at each poutine in turn and order it until the utility gained from it is no larger than ~v~. Repeat this for every poutine. After this point in time, some poutines will give exactly ~v~ utility. If this can account for exactly ~T~ orders, then ~v~ is the correct answer. Otherwise, either it accounts for too many orders, in which case we increase ~v~, or it accounts for too few orders, in which case we decrease ~v~.