Chino has some special preferences toward string.

Now Chino has a string set with strings. She marks each string in the set with specific scores indicated the level of her favor. The special preferences of Chino toward string is when a string with positive score she will like it and with negative score she disgust.

Chino wants to build a new string with  characters, then she want to score this string. The score of new string is calculated by the strings in the set is equal to the sum of each of them occurrences times in new string multiplied respective scores.

Now there is a sample case. In the set there is only contain one string  and scored  points. The new string is . Then the string occurs two times in the new string , so the new string should be scored points.

Now Chino wants to know the maximal score of new string she built.

First input two integers  indicate the length of the new string need built and the size of the strings set.
Then input  lines, string  with respective scores .
Assure  ,  indcate the length of the string.

Output one integer of the maximal score point.

17 3
helloworld 100
ldldl 5
aaa -6

115

The string with maximal score is .