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