Text on the fence
The mayor of Rechuysk has implemented fines for using certain undesirable words and has published a list of these words along with the fine amount for each. All these words are composed of the letters "I", "N", and "W".
Someone is constructing an open fence consisting of N (N ≤ 100) boards. Each board displays one of the letters "I", "N", or "W". The sequence of letters on the fence forms a pattern. For every occurrence of an undesirable word formed by consecutive letters (read from left to right), a fine must be paid, corresponding to the number of times it appears on the fence.
For instance, if the forbidden words are IN with a fine of 1 ruble and WIWI with a fine of 100 rubles, then constructing the fence WIWIWINI would incur a total fine of 201 rubles.
The task is to write a program that determines the sequence of boards for the fence that results in the minimal fine.
Constraints
Fines are given in Rechuysk rubles and are integers ranging from 1 to 100.
The number of forbidden words is at most 50.
The lengths of forbidden words are at most 6 characters.
Input
The first line of the input file contains the length of the fence N, and the second line contains the number of words in the mayor's list M. Each of the following M lines contains an undesirable word followed by its corresponding fine, separated by a space. All words are distinct and consist solely of the uppercase Latin letters "I", "N", or "W".
The input data is guaranteed to be correct.
Output
The first line of the output file should display the value of the minimal fine.