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