`#include `

using namespace std;

//typedef long long int lint;

#define INF 1000000000

int dp[10001];

int coins(int wt,int a[],int v[],int n)

{

if(wt<0)

return INF;

if(wt==0)

return 0;

if(dp[wt]!=INF)

return dp[wt];

for(int i=0;i<n;i++)

{ int k=coins(wt-a*,a,v,n);

if(v*+k<dp[wt])

dp[wt]=v*+k;

}

return dp[wt];

}

int main() {

ios_base::sync_with_stdio(false);

int t;

cin>>t;

while(t–)

{ int e,f;

cin>>e>>f;

int wt=f-e;

for(int i=0;i<wt+1;i++)

dp*=INF;

```
int n;
cin>>n;
int a[n],v[n];
for(int i=0;i<n;i++)
cin>>v*>>a*;
int m=coins(wt,a,v,n);
if(m==INF)
cout<<"This is impossible.
```

";

else

cout<<“The minimum amount of money in the piggy-bank is “<<m<<”.”<<endl;

}

return 0;

}