Migrated from Lutece 51 Food For ACMers

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

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 $N$ yuan 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 \leq N \leq 10^9$) the money Mr. Gou has, and one integer $M$,（$1 \leq M \leq 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 \leq P \leq 10^8$) $S$ stands for the name of the dish and the $P$ is the price of which. The name of the dishes will be unique and guaranteed only include lowercase English letters with the length less 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.

Samples

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

98.50

Resources

电子科技大学第七届ACM程序设计大赛 初赛