1 /*
 2 Author:    Leo.W
 3 Descriptipn:    一個(gè)二維背包的問題，給定升級(jí)上限經(jīng)驗(yàn)n，在忍耐力和殺怪?jǐn)?shù)上限為m與s的情況下，
 4                 面對(duì)所列的k種怪物，每種所獲經(jīng)驗(yàn)a[],消耗忍耐b[]。在能升級(jí)的情況下保留的最多
 5                 忍耐值。不能升級(jí)則輸出-1.
 6 How to Do:    加一維消耗，作完全背包，每種怪的數(shù)量是無限的。
 7   */
 8 #include <stdio.h>
 9 #include <iostream>
10 #include <string.h>
11 using namespace std;
12 #define MAXSIZE 102
13 int DP[MAXSIZE][MAXSIZE];
14 int a[MAXSIZE];
15 int b[MAXSIZE];
16 int main(){
17     //freopen("in.txt","r",stdin);
18     int N,M,K,S;
19     while (scanf("%d%d%d%d",&N,&M,&K,&S)!=EOF){
20         int i,j,k;
21         for(i=0;i<K;i++)    scanf("%d%d",&a[i],&b[i]);
22         memset(DP,0,sizeof(DP));
23         for(i=1;i<=M;i++){
24             for(j=1;j<=S;j++){
25                 for(k=0;k<K;k++){
26                     if(i-b[k]>=0){
27                         if (DP[i-b[k]][j-1]+a[k]>DP[i][j])    
28                             DP[i][j]=DP[i-b[k]][j-1]+a[k];    
29                     }
30                 }
31             }
32             if (DP[i][S]>=N)//當(dāng)滿足升級(jí) 即跳出
33                 break;
34         }
35         if(i>M)    printf("-1\n");
36         else printf("%d\n",M-i);
37     }
38 
39     return 0;
40 } 
41