自己刚开始的想法：一开始就想用最短路做，因为感觉不知道如何表示多维度状态。通过这道题，发现处理多维状态能用的方式自己总结了下：

  1. 多个动态规划结合，优化掉状态，实现O(1)的转移

  2. 切换dp的角度，类似本题从dp资源切换到了dp最大生产力。
    代码：

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,T;
#define MAXN 110
#define MAXT 1010
int A[MAXN],B[MAXN];
int dp[MAXT];
int dp2[MAXT][MAXT];
int main(){
 cin>>N>>M>>T;
 if(M>T) {
     cout<<0<<endl;
     return 0;
 }
 for(int i =1;i<=N;i++){
     cin>>A[i]>>B[i];
 }

 memset(dp,-1,sizeof(dp));
 dp[0] = 0;
 for(int i =1;i<=N;i++){
     for(int j = A[i];j<=T;j++){
         if(dp[j-A[i]]!=-1)
         dp[j] = max(dp[j],dp[j-A[i]]+B[i]);
     }
 }

 memset(dp2,-1,sizeof(dp2)); dp2[0][M] = 0;

 for(int i = 0;i<1000;i++){
     if(dp2[i][T]!=-1){
         cout<<i<<endl;
         return 0;
     }
     for(int j=0;j<=T;j++){
         if(dp2[i][j]==-1) continue;
         for(int k=0;k<=j;k++){
             if(dp[k]==-1) continue;
             if(j-k+dp[k]+dp2[i][j]>=T){
                 cout<<i+1<<endl;
                 return 0;
             }
             if(dp2[i+1][j-k+dp[k]+dp2[i][j]]<dp2[i][j]+dp[k]){
                 dp2[i+1][j-k+dp[k]+dp2[i][j]] = dp2[i][j] + dp[k];
             }
         }
     }
 }
 return 0;
}