题解 | 来硬的(变种背包问题，允许最后一次操作溢出背包)

对于允许最后一次操作溢出背包，在反向遍历（01背包变种），需要进行max(0, j-weight)限制

对于有额外操作的情况，最后不要降维，可能会因为重复访问引起错误，直接二维解决即可。

#include <algorithm>
#include <climits>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
using ll =long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> coal(n);
    for (int i = 0; i < n; i++) cin >> coal[i].first >> coal[i].second;
    
    sort(coal.begin(), coal.end(), [](pair<int, int>& p1, pair<int, int>& p2) {
        return p1.first < p2.first;
    });
    ll minTime = INT_MAX;
    while ( !coal.empty() && coal.back().first * 2 >= m) {
        minTime = min(minTime, static_cast<ll>(coal.back().second / 2));
        coal.pop_back();
    }
    n = coal.size();
    if(n==0) {
        cout<<minTime;
        return 0;
    }
    vector<vector<ll>> dp(n+1,vector<ll>(m+1, INT_MAX)), magic(n+1,vector<ll>(m+1, INT_MAX));
    dp[0][0] = 0;
    magic[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int x = coal[i - 1].first;
        int y = coal[i - 1].second;
        dp[i]=dp[i-1];
        magic[i]=magic[i-1];
        for (int j = m; j >= 0; j--) {
            //no magic
            int k = max(0, j - x);
            if (dp[i-1][k] != INT_MAX) dp[i][j] = min(dp[i][j], dp[i-1][k] + y);
            if (magic[i-1][k] != INT_MAX) magic[i][j] = min(magic[i][j], magic[i-1][k] + y);
            //use magic
            k = max(0, j - 2 * x);
            if (dp[i-1][k] != INT_MAX) magic[i][j] = min(magic[i][j], dp[i-1][k] + y / 2);
            
        }
    }
    cout << min(magic[n][m], minTime);

//cout << magic[n][m];



}
// 64 位输出请用 printf("%lld")