You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in fi * ri(x-1) seconds.


	For example, if fi = 3 and ri = 2, then the tire would finish its 1st lap in 3 seconds, its 2nd lap in 3 * 2 = 6 seconds, its 3rd lap in 3 * 22 = 12 seconds, etc.


You are also given an integer changeTime and an integer numLaps.

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

Return the minimum time to finish the race.

&nbsp;
Example 1:

Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation: 
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.


Example 2:

Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation: 
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. 


&nbsp;
Constraints:


	1 &lt;= tires.length &lt;= 105
	tires[i].length == 2
	1 &lt;= fi, changeTime &lt;= 105
	2 &lt;= ri &lt;= 105
	1 &lt;= numLaps &lt;= 1000


class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        # by observation, we can try to find out the optimal usage within certain numLaps
        # use DP
        # the optimal usage of this lap = min(change tire , no change)
        # dp(laps) = min( dp(laps-1)+dp(1) + dp(laps-2)+dp(2) + ...)
        
        # we don't want to use tires too many laps, which will create unrealistic single lap time
		# we can evaluate single lap time by using changeTime <= 100000 and r >= 2
		# x = minimal continously laps
		# single lap time = 1*2^x <= 100000 -> x can't go more than 19
		limit = 19
        tires = list(set([(t1, t2) for t1, t2 in tires]))
        memo = [[(-1,-1) for _ in range(min(limit,numLaps)+1)] for _ in range(len(tires))]
        
        for i in range(len(tires)):
            for j in range(1, min(limit,numLaps)+1):                   # lap 1 to numLaps
                if j == 1:
                    memo[i][j] = (tires[i][0], tires[i][0])            # total time, lap time
                else:
                    # print('i, j', i, j)
                    tmp = memo[i][j-1][1]*tires[i][1]                  # cost of continuously use tire this lap
                    memo[i][j] = (memo[i][j-1][0]+tmp, tmp)
        
        @cache
        def dp(laps):
            if laps == 1:
                return min(memo[i][1][0] for i in range(len(tires)))
            
            # no change:
            best_time = min(memo[i][laps][0] for i in range(len(tires))) if laps <= limit else float('inf')
            
            # change tire:
			# e.g. change tire at this lap and see if it'll be faster -> dp(laps-1) + changeTime + dp(1)
            # check all previous laps: dp(a) + changeTime + dp(b) until a < b
            for j in range(1, laps):
                a, b = laps-j, j
                if a >= b:
                    ta = dp(a)
                    tb = dp(b)
                    if ta+tb+changeTime < best_time:
                        best_time = ta+tb+changeTime
            return best_time
                
        return dp(numLaps)
class Solution {
    int changeTime;
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        this.changeTime = changeTime;
        int[] minTime = new int[numLaps + 1];
        Arrays.fill(minTime, Integer.MAX_VALUE);

        for (int[] tire : tires){
            populateMinTime(tire, minTime);
        }

        int[] dp = new int[numLaps + 1];
        for (int i = 1; i <= numLaps; i++){
            dp[i] = minTime[i]; // maxValue for dp[i] is Integer.MAX_VALUE, no need to worry about overflow
            for (int j = 1; j < i; j++){
                dp[i] = Math.min(dp[i], dp[j] + changeTime + dp[i - j]); // it will never overflow, since dp[j] are far less than Integer.MAX_VALUE
            }
        }
        return dp[numLaps];
    }

    private void populateMinTime(int[] tire, int[] minTime){
        int sum = 0;
        int base = tire[0];
        int ex = tire[1];
        int spent = 1;
        for (int i = 1; i < minTime.length; i++){
            spent = (i == 1) ? base : spent * ex;
            if (spent > changeTime + base){break;} // set boundary
            sum += spent;
            minTime[i] = Math.min(minTime[i], sum);
        }
    }
}
class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        int n = tires.size();
        // to handle the cases where numLaps is small
        // without_change[i][j]: the total time to run j laps consecutively with tire i
        vector<vector<int>> without_change(n, vector<int>(20, 2e9));
        for (int i = 0; i < n; i++) {
            without_change[i][1] = tires[i][0];
            for (int j = 2; j < 20; j++) {
                if ((long long)without_change[i][j-1] * tires[i][1] >= 2e9)
                    break;
                without_change[i][j] = without_change[i][j-1] * tires[i][1];
            }
            // since we define it as the total time, rather than just the time for the j-th lap
            // we have to make it prefix sum
            for (int j = 2; j < 20; j++) {
                if ((long long)without_change[i][j-1] + without_change[i][j] >= 2e9)
                    break;
                without_change[i][j] += without_change[i][j-1];
            }
        }

        // dp[x]: the minimum time to finish x laps
        vector<int> dp(numLaps+1, 2e9);
        for (int i = 0; i < n; i++) {
            dp[1] = min(dp[1], tires[i][0]);
        }
        for (int x = 1; x <= numLaps; x++) {
            if (x < 20) {
                // x is small enough, so an optimal solution might never changes tires!
                for (int i = 0; i < n; i++) {
                    dp[x] = min(dp[x], without_change[i][x]);
                }
            }
            for (int j = x-1; j > 0 && j >= x-18; j--) {
                dp[x] = min(dp[x], dp[j] + changeTime + dp[x-j]);
            }
        }

        return dp[numLaps];
    }
};
var minimumFinishTime = function(tires, changeTime, numLaps) {  
    const n = tires.length
    const smallestTire = Math.min(...tires.map(t => t[1]))
    const maxSameTire = Math.floor(Math.log(changeTime) / Math.log(smallestTire)) + 1
    const sameTireLast = Array(n).fill(0)
	
	// DP array tracking what is the min cost to complete lap i using same tire
    const sameTire = Array(maxSameTire + 1).fill(Infinity)
    for (let lap = 1; lap <= maxSameTire; lap++) {
        tires.forEach((tire, i) => {
            sameTireLast[i] += tire[0] * tire[1] ** (lap - 1)
            sameTire[lap] = Math.min(sameTire[lap], sameTireLast[i])
        })
    }
    
    const dp = Array(numLaps + 1).fill(Infinity)
    for (let i = 1; i < numLaps + 1; i++) {
        if (i <= maxSameTire) dp[i] = sameTire[i]
		// at each lap, we can either use the same tire up to this lap (sameTire[i])
		// or a combination of 2 different best times, 
		// eg lap 6: use best time from lap 3 + lap 3
		// or from lap 4 + lap 2
		// or lap 5 + lap 1
        for (let j = 1; j < i / 2 + 1; j++) {
            dp[i] = Math.min(dp[i], dp[i-j] + changeTime + dp[j])
        }
    }
    return dp[numLaps]
};
Minimum Time to Finish the Race