class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        // 最大连续圈数：对于 r>=2，指数增长很快，30 圈后时间巨大，换轮胎更优
        // 同时防止溢出，最多计算到 numLaps
        int maxLaps = numLaps;
        long INF = Long.MAX_VALUE / 2; // 防止加法溢出
        long[] cost = new long[maxLaps + 1];
        for (int i = 1; i <= maxLaps; i++) cost[i] = INF;
        
        // 处理 r==1 的情况，记录最小 f
        long minF1 = INF;
        
        for (int[] tire : tires) {
            int f = tire[0];
            int r = tire[1];
            if (r == 1) {
                minF1 = Math.min(minF1, f);
                continue;
            }
            long total = 0;
            long lapTime = f;
            for (int k = 1; k <= maxLaps; k++) {
                total += lapTime;
                if (total >= INF) break; // 超过范围，停止
                if (total < cost[k]) cost[k] = total;
                // 下一圈时间，防止溢出
                if (lapTime > INF / r) break;
                lapTime *= r;
            }
        }
        
        // 用 r==1 的轮胎更新 cost 数组
        if (minF1 != INF) {
            for (int j = 1; j <= maxLaps; j++) {
                long val = minF1 * j;
                if (val < cost[j]) cost[j] = val;
            }
        }
        
        // 动态规划
        long[] dp = new long[numLaps + 1];
        dp[0] = 0;
        for (int i = 1; i <= numLaps; i++) {
            dp[i] = INF;
            for (int j = 1; j <= i; j++) {
                if (cost[j] >= INF) continue;
                long extra = (i - j > 0) ? changeTime : 0;
                if (dp[i - j] + extra + cost[j] < dp[i]) {
                    dp[i] = dp[i - j] + extra + cost[j];
                }
            }
        }
        return (int) dp[numLaps];
    }
}