marathon_dp_ Samsung

#include <iostream>
#include<bits/stdc++.h>
using namespace std;


int dp[1000][1000];

struct race{
    int time_taken;
    int energy;
}speeds[5];

int minTime(int distance_left, int energy_left){
    if(distance_left==0) return 0;

    if(dp[distance_left][energy_left]!=99999) return dp[distance_left][energy_left];

    int ans= 9999999;
    for(int i=0; i<5; i++){
       if(energy_left >= speeds[i].energy){
            int q = speeds[i].time_taken  + minTime(distance_left - 1, energy_left - speeds[i].energy);
            ans=min(ans,q);
       }
   }

   return dp[distance_left][energy_left]=ans;
}

int main() {
    int t=1;
    // cin>>t;
    while(t--){
        int total_energy;
        int distance;
        cin>>total_energy>>distance;

        for(int i=0; i<5; i++)
            cin >> speeds[i].time_taken >> speeds[i].energy;


        for(int i=0; i<1000; i++){
            for(int j=0; j<1000; j++){
                dp[i][j]=99999;
            }
        }

        int ans= minTime(distance,total_energy);
        cout<<ans<<endl;
    }
}

// test case
/*
600 40
191 20
198 16
216 14
221 13
233 12
*/