Мер міста Речуйська розпорядився штрафувати за вживання небажаних слів і обнародуовав список цих слов з разміром штрафу за кожне. Усі ці слова складаються з букв "\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 Перший рядок вихідного файлу повинен містити значення мінімального штрафу.