<p>You are given a <strong>0-indexed</strong> 2D integer array <code>tires</code> where <code>tires[i] = [f<sub>i</sub>, r<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> tire can finish its <code>x<sup>th</sup></code> successive lap in <code>f<sub>i</sub> * r<sub>i</sub><sup>(x-1)</sup></code> seconds.</p>

<ul>
	<li>For example, if <code>f<sub>i</sub> = 3</code> and <code>r<sub>i</sub> = 2</code>, then the tire would finish its <code>1<sup>st</sup></code> lap in <code>3</code> seconds, its <code>2<sup>nd</sup></code> lap in <code>3 * 2 = 6</code> seconds, its <code>3<sup>rd</sup></code> lap in <code>3 * 2<sup>2</sup> = 12</code> seconds, etc.</li>
</ul>

<p>You are also given an integer <code>changeTime</code> and an integer <code>numLaps</code>.</p>

<p>The race consists of <code>numLaps</code> laps and you may start the race with <strong>any</strong> tire. You have an <strong>unlimited</strong> supply of each tire and after every lap, you may <strong>change</strong> to any given tire (including the current tire type) if you wait <code>changeTime</code> seconds.</p>

<p>Return<em> the <strong>minimum</strong> time to finish the race.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
<strong>Output:</strong> 21
<strong>Explanation:</strong> 
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
<strong>Output:</strong> 25
<strong>Explanation:</strong> 
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tires.length &lt;= 10<sup>5</sup></code></li>
	<li><code>tires[i].length == 2</code></li>
	<li><code>1 &lt;= f<sub>i</sub>, changeTime &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= r<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= numLaps &lt;= 1000</code></li>
</ul>

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        # filter function of tires 
        def filter_tires() : 
            # min rate maximizes at 10^5 so 10^6 is sufficiently large to filter 
            # output is the tires we care about 
            min_rate, output = 1_000_000, []
            # for f_i, r_i in tires (sorting means it is in order of minimal f_i not r_i! This is important) 
            for f_i, r_i in sorted(tires) : 
                # if r_i is gte current min rate -> continue 
                if r_i >= min_rate : 
                    continue 
                else : 
                    # otherwise, append to the output and update the min rate 
                    output.append([f_i, r_i])
                    min_rate = r_i 
            # return output when completed 
            return output 
        
        # filter the tires out of the processing 
        tires = filter_tires()
        # figure out your filtered length of tires 
        tL = len(tires) 
        # set up your finished list of tire components 
        finished = [False] * tL 
        # set up your time sums current 
        time_sums = [0] * tL 
        # set up your previous time sums (product multiples here so start with 1) 
        prev_time_sums = [1] * tL
        # set a minimum round times dictionary 
        minimum_round_times = dict() 

        # from first to last lap 
        for l_i in range(1, numLaps + 1) : 
            # find the minimum round time for this lap 
            minimum_round_time = float('inf')
            # by considering all of our tires 
            for t_i in range(tL) : 
                # that we have not already used up 
                if finished[t_i] : 
                    continue 
                else : 
                    # the additional time is the tires at t_i at 0 multiplied by the previous time sums at t_i 
                    # we record and update the prev time sums as specified as we go along 
                    add_time = tires[t_i][0] * prev_time_sums[t_i] 
                    # if lap indix is gt 1 and add_time is gte minimum_round_times[1] + changeTime -> this tire is used
                    if l_i > 1 and add_time >= minimum_round_times[1] + changeTime : 
                        # mark it as used and continue, we got the most out of it 
                        finished[t_i] = True 
                    else : 
                        # otherwise, increment time_sums by the add_time 
                        time_sums[t_i] += add_time 
                        # then multiple the previous time sums by the r_i as needed 
                        prev_time_sums[t_i] *= tires[t_i][1]
                        # now minimize the minimum round time using time sums updated valuation 
                        minimum_round_time = min(minimum_round_time, time_sums[t_i])

            # at end of all t_i, if minimum round time is updated 
            if minimum_round_time < float('inf') : 
                # mark it as such in the dictionary 
                minimum_round_times[l_i] = minimum_round_time 
        
        # set up a dynamic processing array 
        dpa = [float('inf')] * (numLaps + 1) 
        # set the intital to 0 
        dpa[0] = 0 
        # for each lap 
        for l_i in range(1, numLaps + 1) : 
            # for the best of each lap minimum round times 
            for l_j, l_t in minimum_round_times.items() : 
                # if this lap is before the current lap or is the current lap 
                if l_j <= l_i : 
                    # minimize in regards to the prior lap and its time + changeTime (should we have changed the tires?)
                    dpa[l_i] = min(dpa[l_i - l_j] + l_t + changeTime, dpa[l_i])
        # at the end return the dpa at final lap less the changeTime (we'll always do one too many, sadly)
        return dpa[-1] - changeTime
2008