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