#include<bits/stdc++.h> using namespace std; int f[200][200]; int main(){ int n,m,k,s; int a[105],b[105]; while(cin>>n>>m>>k>>s){ for(int i=1;i<=k;i++)cin>>a[i]>>b[i]; memset(f,0,sizeof(f)); for(int i=1;i<=k;i++) for(int j=1;j<=s;j++) for(int k=b[i];k<=m;k++) f[j][k]=max(f[j][k],f[j-1][k-b[i]]+a[i]); int flag=-1; for(int i=0;i<=m;i++) for(int j=1;j<=s;j++) if(f[j][i]>=n){ flag=m-i; i=m+1; break; } cout<<flag<<endl; } }