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

'''
Brute Force: Is to try all combinations of tiles at the xth lap and return the minimum time - O(laps*n!)

Immediately thinking of priority queue

General Idea
- Keep on using the same tire, until the recharge time + fi or fi. ri(x) > next tire in the pq
- The pq should not hold any tires that are recharged - you have to use chargeTime to switch tires anyway
- The problem I'm having is that generally the way the pq should work is if I push in a tire, the other tires in the pq should have an increased time of +5 because you're switching tires so they all incur a +5
- One way to handle this is to push in the next tire but put in a -5 instead so it's like every other tire is being compared with a -5 basically if you use this tire
- But then it gets complicated because if you don't pop this same tire again, you're going to have -5 +5 in a bunch of places
- Oh actually the tires are fresh after every lap basically unless you use the same tire...
- Problem is that switching frequently may not be worth it if chargeTime is high...
- Imagine a case where chargeTime is super high so it forces to stay on a single wheel, but you want to stay on the wheel that has the least ri and not fi necessarily

O(n^2 * lapTime) approach is - dp[i] = dp[j] + changeTime [for j = 1 to tires] and changeTime = 0 if j == i

^ Think about the switching tires or not thing here

Idea is very similar

dp[i] = min(dp[i], dp[j] + changeTime + dp[i - j]), the idea is dp[i] = minimum time to complete ith lap, and you're saying, what if I change my tire at the jth lap and then continue on with the same tire until then? So dp[j] is the minimum time to complete jth lap, and I have i - j laps left, and what's the minimum time if I complete i - j laps? What this allows you to evaluate is, it might be better to switch tires at the jth lap because that means you can complete less laps with i - j and so you'll get a shorter time in exchange for changeTime

Understanding why I can split off tires and numLaps so it's linear time - because I'm thinking I want to calculate how much time it takes for each tire from 1 - numLaps
- Actually this is exactly the math behind 18, because you always want to switch tires after 18th laps with the same tire because in the worst case ri = 2 and 2^19 > changeTime, so you might as well changeTime, note you have to incur the fi cost anyways so even if it's super high, you might as well change the time since it will always be less 
- You're handling the case where you don't change the tire initially...
- Mixing up on the tires
'''
class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        dp = [float('inf')] * (numLaps + 1)
        dp[0] = 0
        
        for f, r in tires:
            prev = 0
            for k in range(1, min(18, numLaps + 1)):
                cur = prev + f * pow(r, k - 1)
                dp[k] = min(dp[k], cur)
                prev = cur
                

  
        for i in range(1, numLaps + 1):
            for j in range(1, min(18, i)):          
                dp[i] = min(dp[i], dp[j] + changeTime + dp[i - j])

        return dp[-1]
            
3591