Текст на огорожі
Мер міста Речуйська розпорядився штрафувати за вживання небажаних слів і обнародуовав список цих слов з разміром штрафу за кожне. Усі ці слова складаються з букв "I", "N", "W".
Дехто будує незамкнену огорожу довжиною N (N ≤ 100) дощок. Є дошки, на кожній з яких написана одна з букв "I", "N" або "W". Отримана огорожа буде міститиь напис з вищеназваних букв. За кожне небажане слово, утворене якими-небудь буквами, що стоять послідовно (при прочитанні зліва направо), прийдеться заплатити штраф, причому стільки разів, скільки разів воно зустрічається на огорожі.
Наприклад, якщо забороненими словами є IN — штраф 1 рубль та WIWI — штраф 100 рублів, то за побудову огорожі WIWIWINI буде призначено штраф 201 рубль.
Потрібно написати програму визначення такої послідовності дощок в огорожі, для якої штраф мінімальний.
Обмеження
Штрафи виражаються у рублях Речуйська і подаються цілими числами від 1 до 100.
Кількість забороненмх слів ≤ 50.
Довжини заборонених слів ≤ 6 символів.
Вхідні дані
Перший рядок файлу вхідних даних містить довжину огорожі N, другий — кількість слів у списку мера M. У кожному з наступних M рядків записано небажане слово і через пропуск — відповідний штраф. Усі слова попарно різні, складаються лише з великих букв латинського алфавіту "I", "N" або "W".
Вхідні даніе коректні.
Вихідні дані
Перший рядок вихідного файлу повинен містити значення мінімального штрафу.