C :: IUST Problem C

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Programming training is an uneasy task which makes the contestants exhausted and staving after a busy training day. UESTC ACM ICPC team has been suffering from go to a chill dinner together because every one may have their own taste of food. For instance, hhb doesn't like spicy food while lxhgww hate dishes containing sugar, love8909 and zhymaoiing despise pepper. To be ridiculous, Hysramp never eat duck. To deal with it, they would never choose the dishes whose name contains "spicy", "sugar", "pepper", "duck". It is Mr. Gou's treat for dinner today and he claims that he has brought only Nyuan in RMB. Everybody wants to use up Mr. Gou's money as greedy as possible without exceed. In addition, every dish could be chosen most once. After the waiter shows the menu, a discussion about order dishes has begun. Can you help them to determine the maximum money can they spend while obeying their taste.

 

Input

The first line of the input contains one integer T, which indicate the number of test cases. The first line of each test case contains one real number N,(0 ≤ N ≤ 10^9) the money Mr. Gou has, and one integer M,(1 ≤ M ≤ 20) indicating the number of dishes they can choose. Following M lines are in format of a string S and a real number P.(0 ≤ P ≤ 10^8) S stands for the name of the dish and the Pis the price of which. The name of the dishes will be unique and guaranteed only include lowercase English letters with the length no more than 20.

 

Output

One line for each test case contains only one real number accurate to two digits after the radix point indicating the answer, the maximum money can they spend while obeying their taste. 

each line may contains more than one input. 

 

Sample Input

1
98.6 6
spicyfish 10.0
supersugar 9.0
riseonly 5.0
lovelyduckling 32.5
kaohongshu 90.0
mengjichi 8.5

Sample Output

98.50

Submit

Source: 12th Iran Nationwide Internet Contest II