408407: GYM103115 A chino with string

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. chino with stringtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

You just output one integer of the maximal score point.

ExampleInput
17 3
helloworld 100
ldldl 5
aaa -6
Output
115
Note

The string with maximal score is "helloworldldldldl".

加入题单

上一题 下一题 算法标签: