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.

Added by:Mateus Dantas [ UFCG ]
Date:2012-02-25
Time limit:0.201s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mateus Dantas

hide comments
2020-03-29 07:42:58
Simple 0/1 knapsak problem keep in mind the format of output can cause WA for you
you can try PARTY and KNAPSAK problems also #HAPPY_CODING :-)
2020-01-03 15:10:38
According to the problem all the bags will have weight >= 8, but there are some inputs where weight is less than 8. So though conceptually for bottom up dp the following loop should work :
for(i = 1; i <= n; i++){ // n is the number of bags
for(j = 8; j <= w; j++){ // w is the maximum capacity
........
}
}
it won't work. You have to start from j = 0 or 1.

Last edit: 2020-01-03 15:10:53
2019-08-15 19:45:13
got runtime error fst 2 times !! but finally accepted....yeeeee
2019-08-06 07:42:41
that bloody "." at the end of cout statement
2019-07-23 20:18:45
Easy knapsack!
My 100th on spoj!!!
2019-07-08 13:22:38
AC in 10000000000000000th go.........
2019-06-24 15:21:20
Why would i help a robber steal ??
2019-06-21 11:43:19
keep an eye on last full stop in output
got one WA bcz of that :-(
easy one :)
2019-02-03 18:40:50
Improperly formatted input

Last edit: 2019-02-15 06:23:57
2019-01-09 19:02:38 Asokan R
Java gives TLE, same code in CPP gives AC!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.