#include<bits/stdc++.h> int f[150][150],w[150],c[150]; int main() { int n, m, kk, s; int i, j, k; int flag, cc; while(scanf("%d %d %d %d", &n, &m, &kk, &s )!=EOF) { flag= 0; memset(f, 0, sizeof(f )); for(i=0; i<kk; i++) { scanf("%d %d", &w[i], &c[i] ); } for(i=0; i<kk; i++) { for(j=c[i]; j<=m; j++) { for(k=1; k<=s; k++) { if(f[j][k] < (f[j-c[i]][k-1] + w[i]) ) { f[j][k] = f[j-c[i]][k-1] + w[i] ; } } } } for(i=0; i<=m; i++) { for(j=1; j<=s; j++) { if( f[i][j] >=n ) { flag=1; cc = i; break; } } if(flag==1) break; } if(flag) printf("%d\n", m-cc); else printf("-1\n"); } return 0; }