/* -*- coding: utf-8 -*- * * 3713.cc: No.3713 豬キ蠎墓爾邏「 - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 100; const int MAX_A = 100; /* typedef */ /* global variables */ int xs[MAX_N], ys[MAX_N]; int dp[MAX_N + 1][MAX_A + 1]; /* subroutines */ void setmin(int &a, int b) { if (a > b) a = b; } /* main */ int main() { int n, a, b; scanf("%d%d%d", &n, &a, &b); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); for (int j = 0; j <= n; j++) fill(dp[j], dp[j] + (a + 1), b + 1); dp[0][0] = 0; for (int i = 0; i < n; i++) for (int j = n - 1; j >= 0; j--) for (int k = a - xs[i]; k >= 0; k--) if (dp[j][k] <= b) setmin(dp[j + 1][k + xs[i]], dp[j][k] + ys[i]); int maxj = n; while (maxj > 0) { if (*min_element(dp[maxj], dp[maxj] + (a + 1)) <= b) break; maxj--; } printf("%d\n", maxj); return 0; }