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