<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:
        pass



        




















class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        # Step 1: Precompute the best time to finish consecutive laps using the same tire
        max_laps = 1000  # Max number of laps
        INF = float('inf')
        
        # min_time_for_laps[i] will store the minimum time to complete i laps with any single tire
        min_time_for_laps = [INF] * (max_laps + 1)
        
        # iterate over all tire types and number of laps. 
        for f, r in tires:
            time = f # time for the next single lap
            total_time = f
            for lap in range(1, max_laps + 1):
                if time > f + changeTime:
                    # if this is the case, just replace the new tire of the same type. 
                    # f + changeTime: the time for a single lap after replacing to the new tire.
                    # time: time for the next single lap without replacing tire.
                    break
                min_time_for_laps[lap] = min(min_time_for_laps[lap], total_time)
                time *= r
                total_time += time
        
        # Step 2: Dynamic Programming to find minimum time for exactly numLaps
        dp = [INF] * (numLaps + 1)
        dp[0] = 0
        # dp[i] = t --> minimum time required to run i-laps. 
        
        for lap in range(1, numLaps + 1):
            for k in range(1, lap + 1):
                # When rotating for lap number of laps, divide it into two parts:
                #   1~k laps: with No replacing tires
                #   k~lap laps: with possible replacing tires
                # Compare this divided case (dp[lap - k] + min_time_for_laps[k] + changeTime) 
                #   to the existing time (dp[lap]), and find minimum. 
                dp[lap] = min(dp[lap], dp[lap - k] + min_time_for_laps[k] + changeTime)
        
        return dp[numLaps] - changeTime





class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        max_laps = 1000

        min_time_for_laps = [float('inf')] * (max_laps+1)
        for f, r in tires:
            lap_time = f
            total_time = f
            for lap in range(1, max_laps+1):
                if lap_time > changeTime + f:
                    break
                min_time_for_laps[lap] = min(min_time_for_laps[lap], total_time)
                lap_time *= r
                total_time += lap_time

        dp = [float('inf')] * (numLaps+1)
        dp[0] = 0
        for lap in range(1, numLaps+1):
            for k in range(1, lap+1):
                if k == lap:
                    dp[lap] = min(dp[lap], min_time_for_laps[k])
                else:
                    dp[lap] = min(dp[lap], dp[lap-k] + min_time_for_laps[k] + changeTime)
        return dp[numLaps]



class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        max_laps = numLaps+10

        min_time_for_laps = [float('inf')] * (max_laps+1)
        for f, r in tires:
            lap_time = f
            total_time = f
            for lap in range(1, max_laps+1):
                if lap_time > changeTime + f:
                    break
                min_time_for_laps[lap] = min(min_time_for_laps[lap], total_time)
                lap_time *= r
                total_time += lap_time

        dp = [float('inf')] * (numLaps+1)
        dp[0] = 0
        for lap in range(1, numLaps+1):
            for k in range(1, lap+1):
                if k == lap:
                    dp[lap] = min(dp[lap], min_time_for_laps[k])
                else:
                    dp[lap] = min(dp[lap], dp[lap-k] + min_time_for_laps[k] + changeTime)
        return dp[numLaps]


class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        min_time_for_laps = [float('inf')] * (numLaps+1)
        for f, r in tires:
            lap_time = f
            total_time = f
            for lap in range(1, numLaps+1):
                if lap_time > changeTime + f:
                    break
                min_time_for_laps[lap] = min(min_time_for_laps[lap], total_time)
                lap_time *= r
                total_time += lap_time
        
        dp = [float('inf')] * (numLaps+1)
        dp[0] = 0
        for lap in range(1, numLaps+1):
            for k in range(1, lap+1):
                if k == lap:
                    dp[lap] = min(dp[lap], min_time_for_laps[lap])
                else:
                    dp[lap] = min(dp[lap], min_time_for_laps[k] + dp[lap-k] + changeTime)
        return dp[numLaps]
3214