class Solution {
public:
    int power(int base, int power)
    {
        int ans=1;
        while(power)
        {
            if(power%2)
                ans*=base,power--;
            else
                base*=base,power/=2;
        }
        return ans;
    }
    
    int solve(int idx, int num, int lapno, vector<vector<int>>& tires, int& change,  vector<vector<vector<int>>>& dp)
    {
       if(idx>=tires.size() && num==0)
           return 0;
        

       if(idx>=tires.size())
           return 1e9;
        
       if(num==0)
           return 0; 
       
       if(dp[idx][num][lapno]!=-1)
           return dp[idx][num][lapno];
       
       // not take the current tire and move to next tire 
       int ans1=solve(idx+1,num,1,tires,change,dp);
        
       // take the current tire without change time 
       int ans2=tires[idx][0]*power(tires[idx][1],lapno-1)+solve(idx,num-1,lapno+1,tires,change,dp);
        
       // take the current tire with change time 
       int ans3=change+tires[idx][0]+solve(idx,num-1,2,tires,change,dp);
        
       // apply change time and move to next tire 
       int ans4=change+solve(idx+1,num,1,tires,change,dp);
         
       return dp[idx][num][lapno]=min({ans1,ans2,ans3,ans4}); 
    }
    
    int minimumFinishTime(vector<vector<int>>& tires, int change, int num) {
        int n=tires.size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(1001,vector<int>(1001,-1)));
        return solve(0,num,1,tires,change,dp);
    }
};