题解 | #消灭怪物#

#include <iostream>
#include<vector>
using namespace std;

int ans= 1e6;

void dfs(int curBlood,int curtimes,int n,vector<bool> &vic,vector<int> &hurt,vector<int> &blood){
    if(curBlood<=0){
        ans=ans<curtimes?ans:curtimes;
        return;
    }

    for(int i=0;i<n;i++){
        if(vic[i]){
            continue;
        }
        vic[i]=true;
        int nextBlood=curBlood;
        if(curBlood<=blood[i]){
            nextBlood-=hurt[i]*2;
        }
        else nextBlood-=hurt[i];
        dfs(nextBlood, curtimes+1, n, vic,hurt,blood);
        vic[i]=false;

    }

}


int main() {
    int T;
    cin>>T;
    while(T--){
        int n,m,i=0;
        cin>>n>>m;
        vector<int> hurt;
        vector<int> blood;
        while(i<n){
            int A,x;
            cin>>A>>x;
            hurt.push_back(A);
            blood.push_back(x);
            i++;
        }
        ans=1e6;
        vector<bool> isvic(n,false);
        dfs(m, 0, n, isvic, hurt, blood);
        if(ans==1e6) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")