Задачі
Текст на огорожі
Текст на огорожі
Мер міста Речуйська розпорядився штрафувати за вживання небажаних слів і обнародуовав список цих слов з разміром штрафу за кожне. Усі ці слова складаються з букв "\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
Перший рядок вихідного файлу повинен містити значення мінімального штрафу.
Вхідні дані #1
8 8 W 10 I 10 N 30 WI 1 WW 10 II 11 WIW 2 IWI 3
Вихідні дані #1
98