1 /*
 2 Author:    Leo.W
 3 Descriptipn:    一個二維背包的問題，給定升級上限經驗n，在忍耐力和殺怪數上限為m與s的情況下，
 4                 面對所列的k種怪物，每種所獲經驗a[],消耗忍耐b[]。在能升級的情況下保留的最多
 5                 忍耐值。不能升級則輸出-1.
 6 How to Do:    加一維消耗，作完全背包，每種怪的數量是無限的。
 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)//當滿足升級 即跳出
33                 break;
34         }
35         if(i>M)    printf("-1\n");
36         else printf("%d\n",M-i);
37     }
38 
39     return 0;
40 } 
41