1 #include<iostream> 2 #include<memory.h> 3 #include<cstdio> 4 using namespace std; 5 #define maxp 102  //经验值 6 #define maxv 102  //种类 7 #define Max(i,j) i > j? i : j 8 int dp[maxp][maxv]; 9 int p[maxp];  //杀掉所消耗的忍耐值10 int w[maxv];  //杀掉所获经验值11 int expe,pati,num,maxkill;12 void d()13 {14     int i,j,l;15     memset(dp,0,sizeof(dp));16     for(int i = 0; i < num; i++)17             cin>>w[i]>>p[i];18     for(i = 0; i < num; i++)//k个种类 遍历19     {20         for(j = p[i]; j <= pati; j++)21         {22             for(l = 1; l <= maxkill; l++)23             {24                 dp[j][l] = Max(dp[j][l], dp[j - p[i]][l - 1] + w[i]);25             }26         }27     }28     int flag = 0;29     int pos;30     for(int i = 0; i <= pati; i++)31     {32         for(int j = 1; j <= maxkill; j++)33         {34             if(dp[i][j] >= expe)35             {36                 flag = 1;37                 pos = i;38                 break;39             }40         }41         if(flag)break;42     }43     if(flag)cout<<pati - pos<<endl;44     else cout<<"-1"<<endl;45 }46 int main()47 {48     freopen("input.txt","r",stdin);49     while(cin>>expe>>pati>>num>>maxkill)50     {51 52         d();53     }54     return 0;55 }