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.
hide comments
davidgalehouse:
20190203 18:40:50
Improperly formatted input Last edit: 20190215 06:23:57 

Asokan R:
20190109 19:02:38
Java gives TLE, same code in CPP gives AC! 

golu20174024:
20180710 16:42:59
knapsack classical problem


richardks3647:
20180628 03:12:43
the period at the end ;) 

vivek_rathi:
20180318 15:36:44
simple Knapsack Problem .


nadstratosfer:
20180227 15:08:11
Pythonists go practice DP on KNAPSACK and PIGBANK instead, the TL here is near impossible to pass. Ensure your solution can handle blanklines and other garbage in input if you insist to try. 2 thumbs down for this turd of a problem. 

prasanth292130:
20180114 09:30:34
Damn fullstop


abhar10:
20171117 00:12:30
Simple Knapsack Problem.


coolio_1:
20170625 16:00:35
Easy  Peasy!


vaifai:
20170515 17:20:46
My code in java is getting NZEC .What should i do?

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