1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6  7 const int maxn = 105; 8 int dp[maxn][maxn]; 9 int a[maxn], b[maxn];10 11 int main() {12     int n, m, s, k;13     while(EOF != scanf("%d %d %d %d",&n, &m, &k, &s) ) {14         for(int i = 1; i <= k; i++) {15             scanf("%d %d",&a[i], &b[i]);16         }17         memset(dp, 0, sizeof(dp));18         for(int i = 1; i <= k; i++) {19             for(int j = b[i]; j <= m; j++) {20                 for(int l = 1; l <= s; l++) {21                     dp[j][l] = max(dp[j][l], dp[j - b[i]][l - 1] + a[i]);22                 }23             }24         }25         int ans = -1;26         for(int j = 0; j <= m; j++) {27             for(int l = 0; l <= s; l++) {28                 if(dp[j][l] >= n) {29                     ans = max(ans, m - j);30                 }31             }32         }33         printf("%d\n", ans);34     }35     return 0;36 }