408407: GYM103115 A chino with string

Chino has some special preferences toward string.

Now Chino has a string set with $$$m$$$ 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 $$$n$$$ 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 "aaa" and scored 3 points. The new string is "aaaa". Then the string "aaa" occurs two times in the new string , so the new string should be scored 6 points.

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

First input two integers $$$n,m(1 \leq n \leq 10^9,1 \leq m \leq 200)$$$ indicate the length of the new string need built and the size of the strings set.

Then input m strings named s with respective scores $$$v(-10^6 \leq v \leq 10^6)$$$.

Assure $$$ \sum \left | s \right | \leq 200 $$$ , $$$ \left | s \right | $$$ indcate the length of the string.

You just output one integer of the maximal score point.

17 3
helloworld 100
ldldl 5
aaa -6

115

The string with maximal score is "helloworldldldldl".