## WACHOVIA - Wachovia Bank

Danilo Gheyi is a renowned bank robber. He is known worldwide for accomplishing the most profitable bank robbery, in Fortaleza, Ceará. Danilo and his friends dug a tunnel to get into the main chest. There were some bags, with different amounts of money or jewelry and weight. They had to leave about 50% of the total value, since the truck couldn't carry all the bags.

Danilo wasn't caught, and to show that he can do itall again, he is planning a robbery to one of the safer banks in USA -the Wachovia Bank. He wants your help to maximize the amount stolen, avoiding a huge loss as it happened in Fortaleza.

Write a program that, given the maximum weight the truck is ableto carry and the information about each bag in the bank, determine the maximum value that Danilo can steal.

### Input

The input consists of several instances. There is an integer N (1 ≤ N ≤ 200) in the first line; it stands for the number of instances. The first line of each instance contains two integers, K and M (8 ≤ K ≤ 1000 and 1 ≤ M ≤ 50) representing, respectively, the maximum weight the truck can handle and the amount of bags in the bank. The next M lines describe each bag with two integers A and B (8 ≤ A ≤ 200 and 1 ≤ B ≤ 25): the weight and the value of the bag, respectively.

### Output

For each instance output a sentence “Hey stupid robber, you can get P.”, and P represents the maximum value Danilo can steal.

### Example

```Input:
3
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2

Output:
Hey stupid robber, you can get 8.
Hey stupid robber, you can get 25.
Hey stupid robber, you can get 99.```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb   push_back
#define EPS 1e-9
#define FOR(i,n)  for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b)   si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
int wt[55];
int value[55];
int dp[1005][55];

int f(int W, int n){
if(n == 0)
return 0;
if(dp[W][n] != -1)
return dp[W][n];
if(wt[n-1] > W){
dp[W][n] = f(W, n-1);
return dp[W][n];
}
dp[W][n] = max(value[n-1] + f(W-wt[n-1], n-1), f(W, n-1));
return dp[W][n];
}

int main(){
io;
int t;
cin >> t;
while(t--){
memset(dp, -1, sizeof(dp));
int W, n;
cin >> W >> n;
for(int i = 0;i < n; i++){
cin >> wt[i] >> value[i];
}
int ans = f(W, n);
cout << "Hey stupid robber, you can get ";
cout << ans << "." <<endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
3
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2

Output

cmd
Hey stupid robber, you can get 8.
Hey stupid robber, you can get 25.
Hey stupid robber, you can get 99.

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.util.*;
import java.math.*;
import java.io.*;
class Wachovia
{
public static void main(String args [])	throws IOException
{
PrintWriter pw=new PrintWriter(System.out, true);

int W=Integer.parseInt(str[0]);
int n=Integer.parseInt(str[1]);
int val=0,wt=0;
int max=W;int ans[][]=new int [3][max+1];
int mar[][]=new int[2] [max+1];
int last=0,use=0;
//int small=Integer.MAX_VALUE;
for(int j=1; j<=n; j++)
{
val=Integer.parseInt(si[0]);wt=Integer.parseInt(si[1]);
int jmt=j%3,jit=(j-1)%3;last=jmt;
//small=small<wt?small:wt;
for(int k=wt; k<=max; k++)
{
/*if(wt>k)
{ans[jmt][k]=ans[jit][k];}
else*/
//ans[jmt][k]=Math.max((val+ans[jit][k-wt]),ans[jit][k]);
if(j%2!=0)
{//pw.print(mar[0][k]+" "+mar[0][k-wt]+"GF");
ans[jmt][k]=Math.max((val+mar[0][k-wt]),mar[0][k]);
mar[1][k]=mar[1][k]>ans[jmt][k]?mar[1][k]:ans[jmt][k];

}
else
{
//pw.print(mar[1][k]+" "+mar[1][k-wt]+"GF");
ans[jmt][k]=Math.max((val+mar[1][k-wt]),mar[1][k]);
mar[0][k]=mar[0][k]>ans[jmt][k]?mar[0][k]:ans[jmt][k];
pw.print(mar[0][k]+" ");
}
}
pw.println();
}
System.out.println( ans[last][max]);

}
}``````
Copy The Code &

Input

cmd
3
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2

Output

cmd
Hey stupid robber, you can get 8.
Hey stupid robber, you can get 25.
Hey stupid robber, you can get 99.