1 #include<stdio.h> 2 #include<string.h> 3 int d[101][101]; 4 int main() 5 { 6 int i,j,t,flag,v,w,n,m,k,s; 7 while(~scanf("%d%d%d%d",&n,&m,&k,&s)){ 8 memset(d,0,sizeof(d)); 9 for(flag=i=0;i<k;++i){ 10 scanf("%d%d",&v,&w); 11 for(j=w;j<=m;++j) 12 for(t=1;t<=s;++t) 13 d[j][t]>?=d[j-w][t-1]+v; 14 } 15 for(flag=i=0;i<=m;++i) 16 if(d[i][s]>=n){ 17 flag=1; 18 break; 19 } 20 if(flag) printf("%d\n",m-i); 21 else puts("-1"); 22 } 23 return 0; 24 }