すぬけ君が食べる料理の集合からすぬけ君が最後に食べる料理を除いた集合について、そこに含まれる料理の甘さの合計・しょっぱさの合計はそれぞれ \(X\) 以下・\(Y\) 以下である（＊）ことに着目します。

甘さの合計が \(X\) を超えず、かつしょっぱさの合計が \(Y\) を超えないようにいくつかの料理の集合 \(S\) を選ぶとき、\(S\) に含まれる料理の個数の最大値を \(x\) とします。このとき、元の問題の答えは \(\min(x+1, N)\) と表せます。（証明：\(x=N\) のとき明らか。\(x<N\) のとき、\(S\) に含まれる料理を先に並べることで最低 \(x+1\) 個は食べられ、逆に \(x+2\) 個食べられたとすると（＊）より要素数 \(x+1\) の \(S\) が取れることとなって矛盾。よって食べられる料理の個数の最大値は \(x+1\)。）

では、甘さの合計が \(X\) を超えず、かつしょっぱさの合計が \(Y\) を超えないという条件のもとで選べる料理の個数の最大値を計算することを考えましょう。一番簡単なアプローチは以下のような DP を用いることですが、計算量が \(O(NXY)\) となって間に合いません：

• \(dp_{i,j,k}=(\) 料理 \(1,2,\dots,i\) の中から甘さの合計が \(j\)、しょっぱさの合計が \(k\) となるようにいくつか料理を選ぶとき、選ぶ料理の個数の最大値）

そこで、本問題においては \(N\) の値が \(X,Y\) より小さいことに着目して、DP のキーと値を入れ替えるという典型的なアプローチを用います。具体的には、選ぶ料理の個数をキーに、しょっぱさの合計を値に持ってきて、

• \(dp'_{i,j,k}=(\) 料理 \(1,2,\dots,i\) の中から甘さの合計が \(j\) となるように \(k\) 個の料理を選ぶとき、しょっぱさの合計の最小値）

とすれば、\(O(N^2X)\) の計算量で DP テーブルを埋めることができます。あとは、\(dp'_{N,j,k} \leq Y\) を満たす \(j\) が存在するような \(k\) の最大値を求めれば良いです。

実装例 (C++) （ 注 : 解説本文と本実装例では DP の \(2,3\) 番目のキーが表すものが入れ替わっています）:

#include <bits/stdc++.h>

using namespace std;

void chmin(int &a, int b) { a = min(a, b); }

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    vector dp(n + 1, vector(n + 1, vector<int>(x + 1, 1e9)));
    dp[0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= x; k++) {
                chmin(dp[i + 1][j][k], dp[i][j][k]);
                if (k + a[i] <= x) {
                    chmin(dp[i + 1][j + 1][k + a[i]], dp[i][j][k] + b[i]);
                }
            }
        }
    }
    for (int i = n; i >= 0; i--) {
        for (int j = 0; j <= x; j++) {
            if (dp[n][i][j] <= y) {
                cout << min(i + 1, n) << endl;
                return 0;
            }
        }
    }
}