#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 1, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
// ----------------------------------------------------------------
// 贪心策略：有券的情况下，优先选择q小p大；没有卷优先选择p小的
// 该策略可以通过大部分数据，但是会 wa
// 时间复杂度 ：O(nlog_n)
namespace A {
ll n, k, m, ans = 0;
bool st[N];
struct T {
    ll p, q, i;
} a[N];
int P = 1e4;
int solve() {
    cin >> n >> k >> m;
    for (int i = 1, p, q; i <= n; i++)
        cin >> p >> q, a[i] = {p, q, i}, assert(p <= P), assert(q <= P);

    sort(a + 1, a + 1 + n, [&](T& l, T& r) {
        if (l.q != r.q)
            return l.q < r.q;
        return l.p > r.p;
    });
    for (ll i = 1; i <= min(k, n); i++)
        if (m >= a[i].q && !st[a[i].i]) {
            m -= a[i].q, st[a[i].i] = 1, ans++;
            if (a[i].p == a[i].q)
                k++;
        }
    sort(a + 1, a + 1 + n, [&](T& l, T& r) { return l.p < r.p; });
    for (ll i = 1; i <= n; i++)
        if (m >= a[i].p && !st[a[i].i]) {
            m -= a[i].p, st[a[i].i] = 1, ans++;
        }
    cout << ans << endl;
    return 0;
}
}  // namespace A
// ----------------------------------------------------------------
// 二维费用背包
// dp[i][j][k] 对于前i件物品用劵不超过j，现金不超过k能获得的最大数量
// 该方法可以通过大部分数据，但是会 MLE,TLE,RTE
// 时间复杂度 ：O(nkm)
namespace B {
const int M = 660;
ll p[N], q[N];
int f[M][M][M], x = 0, ans = 0;
ll n, m, num;
int solve() {
    // memset(f, 0x00, sizeof f);
    cin >> n >> num >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> q[i];
        // if (p[i] == q[i] && p[i] == 0)
        //     x++, p[i] = q[i] = 9e18;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= num; j++) {
            for (int k = 0; k <= m; k++) {
                int& t = f[i][j][k];
                t = max(t, f[i - 1][j][k]);
                if (k >= p[i])
                    t = max(t, f[i - 1][j][k - p[i]] + 1);
                if (j >= 1 && k >= q[i])
                    t = max(t, f[i - 1][j - 1][k - q[i]] + 1);
                ans = max(ans, t);
            }
        }
        // cout << i << " " << ans + x << endl;
    }
    cout << ans + x;
    return 0;
}
}  // namespace B
// ----------------------------------------------------------------
// 二维费用背包状态压缩
// 时间复杂度不变，空间优化，仍会 MLE,TLE,RTE
namespace C {
const int K=5e4+1, M = 4001;
ll p[N], q[N];
int x = 0, ans = 0;
ll n, m, num;
int solve() {
    cin >> n >> num >> m;
    vector<vector<int>> f(num+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++) cin >> p[i] >> q[i];
    for (int i = 1; i <= n; i++) {
        for (int j = num; j>=0; j--) {
            for (int k = m; k>=0; k--) {
                int& t = f[j][k];
                if (k >= p[i])
                    t = max(t, f[j][k - p[i]] + 1);
                if (j >= 1 && k >= q[i])
                    t = max(t, f[j - 1][k - q[i]] + 1);
                ans = max(ans, t);
            }
        }
        // cout << i << " " << ans + x << endl;
    }
    cout << ans + x;
    return 0;
}
}  // namespace C
// ----------------------------------------------------------------
/*
贪心：问题具有最优子结构性质——等一下，好像不太对
DP：问题本质就是一个选择购买和不选择购买的一个问题
*/
int main() {
    // A::solve();
    // B::solve();
    C::solve();
}

注意

之前的代码被 $Hack$ 了，主要是遗漏了对 $p$ 排序，即使用优惠卷时，在 $q$ 相同的情况先购买 $p$ 大的。

贪心策略1：将所有衣服优惠前后都加放入堆中，接下来维护一些信息

• 堆排序的原则：按照优惠后价格升序，如果优惠后价格相同，那么按照优惠前降序。
• 优惠前后的同一件衣服只能买一次
• 剩余现金
• 剩余优惠券数量

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, k, m, ans;
bool st[N];
struct T {
    int p, q, i;
    bool operator<(const T& r) const { 
        if(p!=r.p) return p > r.p; 
        return q < r.q;
    }
};
priority_queue<T> qu;
int main(int argc, char* argv[]) {
    cin >> n >> k >> m;
    for (int i = 1, p, q; i <= n; i++)
        cin >> p >> q, qu.push({p, q, i}), qu.push({q, p, i});
    while (qu.size()) {
        auto u = qu.top(); qu.pop();
        if (st[u.i] || m < u.p) continue;
        if (u.q > u.p && k == 0) continue;
        if (u.q > u.p) k--;
        m -= u.p, st[u.i] = 1, ans++;
    }
    cout << ans << endl;
    return 0;
}

贪心策略2：先按优惠后价格从小到大排，如果优惠后的价格相同，那么按照优惠前价格从大到小排，买完可使用优惠券的直到不能购买为止；再按优惠前价格从小到大排，直到不能购买为止。如果使用优惠价前后价格相同，那么看作不使用优惠券。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
ll n, k, m, ans;
bool st[N];
struct T {
   ll p, q, i;
} a[N];
int P = 1e4;
int main(int argc, char* argv[]) {
   cin >> n >> k >> m;
   for (int i = 1, p, q; i <= n; i++)
       cin >> p >> q, a[i] = {p, q, i}, assert(p <= P), assert(q <= P);

   sort(a + 1, a + 1 + n, [&](T& l, T& r) {
       if (l.q != r.q)
           return l.q < r.q;
       return l.p > r.p;
   });
   for (ll i = 1; i <= min(k, n); i++)
       if (m >= a[i].q && !st[a[i].i]) {
           m -= a[i].q, st[a[i].i] = 1, ans++;
           if (a[i].p == a[i].q)
               k++;
       }
   sort(a + 1, a + 1 + n, [&](T& l, T& r) { return l.p < r.p; });
   for (ll i = 1; i <= n; i++)
       if (m >= a[i].p && !st[a[i].i]) {
           m -= a[i].p, st[a[i].i] = 1, ans++;
       }
   cout << ans << endl;
   return 0;
}