Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "\textbf{I}", "\textbf{N}", "\textbf{W}". Некто строит незамкнутый забор длиной \textbf{N} (\textbf{N} ≤ \textbf{100}) досок. Имеются доски, на каждой из которых написана одна из букв "\textbf{I}", "\textbf{N}" или "\textbf{W}". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе. Например, если запрещенными словами являются \textbf{IN} --- штраф \textbf{1} рубль и \textbf{WIWI} --- штраф \textbf{100} рублей, то за построение забора \textbf{WIWIWINI} будет назначен штраф \textbf{201} рубль. Требуется написать программу определения такой последовательности досок в заборе, для которой штраф минимален. \textit{\textbf{Ограничения}} \begin{itemize} \item Штрафы выражаются в рублях Речуйска и представляются целыми числами от \textbf{1} до \textbf{100}. \item Количество запрещенных слов ≤ \textbf{50}. \item Длины запрещенных слов ≤ \textbf{6} символов. \end{itemize} \InputFile Первая строка файла входных данных содержит длину забора \textbf{N}, вторая --- количество слов в списке мэра \textbf{M}. В каждой из последующих \textbf{M} строк записано нежелательное слово и через пробел --- соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "\textbf{I}", "\textbf{N}" или "\textbf{W}". Входные данные корректны. \OutputFile Первая строка выходного файла должна содержать значение минимального штрафа.