#include <bits/stdc++.h> using namespace std; int dp[101][101]; int a[101]; int p[101]; int main() { int n, m, s, k; while(scanf("%d%d%d%d", &n, &m, &k, &s)!=EOF) { memset(dp, 0, sizeof(dp)); for(int i=0; i<k; i++) { scanf("%d%d", &a[i], &p[i]); } int ans=-1; for(int i=0; i<k; i++) { for(int j = p[i]; j<=m; j++) { for(int l = 1; l<=s; l++) { dp[j][l]=max(dp[j][l], dp[j-p[i]][l-1]+a[i]); } } } if(dp[m][s]>=n) { for(int i=0; i<=m; i++) { if(dp[i][s]>=n) { ans=m-i; break; } } } cout << ans << endl; } return 0; }