#include<iostream> #include<cstring> using namespace std; int a[101],b[101]; int dp[101][101]; int main(){ int n,m,k,s; while(cin>>n>>m>>k>>s){ memset(dp,0,sizeof(dp)); for(int i=1;i<=k;i++){ cin>>a[i]>>b[i]; } for(int i=1;i<=k;i++){ for(int u=1;u<=s;u++){ for(int v=b[i];v<=m;v++){ dp[u][v]=max(dp[u][v],dp[u-1][v-b[i]]+a[i]); } } } int f=-1; for(int u=0;u<=m;u++){ for(int v=1;v<=s;v++){ if(dp[v][u]>=n){ f=m-u; u=m+1; break; } } } cout<<f<<endl; } return 0; }