// //完全背包问题 //DP[v]为重量为v的钱罐最少有多少钱 //DP[v] = min{DP[v],DP[v-W[i]] + P[i]} //其实就是 DP[i,v] = min{DP[i-1,v],DP[i,v-W[i]] + P[i]} //也可以用贪心来做 #include <iostream> #include <cstring> #define INF 9999999 using namespace std; int T; int E,F; int N; long P[50001],W[10001]; long DP[10001]; int main() { cin>>T; while(T--) { cin>>E>>F; cin>>N; for(int i = 1; i <= N; i++) { cin>>P[i]>>W[i]; } memset(DP,INF,sizeof(DP)); DP[0] = 0; for(int i = 1; i <= N; i++) { for(long j = W[i]; j <= F-E; j++) { DP[j] = min(DP[j],DP[j-W[i]] + P[i]); } } if(DP[F-E] < INF) cout<<"The minimum amount of money in the piggy-bank is "<<DP[F-E]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }