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