#include<iostream> using namespace std; const int N = 1e2 + 10; int n, m, k, s, a[N], b[N], f[N][N]; int main(){ while(cin >> n >> m >> k >> s){ for(int i = 0; i < k; i++) cin >> a[i] >> b[i]; int ans = -1; for(int i = 0; i < k; i++){ for(int j = 0; j <= m; j++){ for(int l = 1; l <= s; l++){ if(j >= b[i]){ f[j][l] = max(f[j][l], f[j-b[i]][l-1] + a[i]); } } } } for(int i = 0; i <= m; i++){ for(int j = 1; j <= s; j++){ if(f[i][j] >= n){ ans = m - i; i = m + 1; break; } } } cout << ans << endl; } return 0; }