#include#include #include using namespace std; const int INF = 0x3f3f3f3f; int dp[110][110]; int main() { int n,m,k,s; int c[110],w[110]; while(~scanf(%d %d %d %d,&n,&m,&k,&s)) { for(int i = 1; i <= k; i++) scanf(%d %d,&w[i],&c[i]); for(int i = 0; i <= m; i++) { for(int j = 0; j <= s; j++) { if(j == 0) dp[i][j] = 0; else dp[i][j] = -INF; } } for(int i = 1; i <= k; i++) { for(int j = c[i]; j <= m; j++) { for(int g = 1; g <= s; g++) { dp[j][g] = max(dp[j][g], dp[j-c[i]][g-1]+w[i]); } } } int f = 0; for(int i = 0; i <= m; i++) { for(int j = 0; j <= s; j++) { if(dp[i][j] >= n) { printf(%d ,m-i); f = 1; break; } } if(f == 1) break; } if(!f) printf(-1 ); } return 0; }