Scrabble Flash

Scrabble Flash 게임에서는 5개의 글자 타일이 주어지고, 제한 시간이 끝나기 전에 가능한 한 많은 단어를 찾아야 한다. 이 버전에서는 버튼을 누르면 타일의 글자를 원하는 다른 글자로 바꿀 수 있다. 글자를 바꾸는 데는 시간이 들므로, 글자 변경은 가능한 한 줄이는 것이 좋다.

플레이어들은 방금 찾은 단어와 비슷한 단어를 찾는 것이 그렇지 않은 단어를 찾는 것보다 훨씬 쉽다는 점을 알고 있다. 플레이어들은 가장 최근에 찾은 단어를 바탕으로 다음 단어를 찾는 데 걸리는 시간을 다음과 같이 추정한다. $w$를 찾는 단어의 길이, $s$를 두 단어의 최장 공통 부분 문자열 길이라 하면, 걸리는 시간(초)은 다음과 같다.

$\frac{w (w+1)}{2} - \frac{s(s+1)}{2}$

단어 목록이 주어졌을 때, 주어진 초 안에 찾을 수 있는 단어의 최대 개수를 구하라.

첫째 줄에 공백으로 구분된 두 정수 $U$(초 단위 시간)와 $N$(고려할 단어의 개수)이 주어진다($0 \leq U \leq 100$, $1 \leq N \leq 10$). 이어서 $N$개의 줄에 각각 길이 1 이상 5 이하의 소문자 a부터 z로 이루어진 단어가 하나씩 주어진다. 첫 번째 단어는 시작 단어이며, 0초에 찾은 것으로 본다. $N$개의 단어는 모두 서로 다르다.

주어진 초 안에 찾을 수 있는 단어의 최대 개수를 한 줄에 출력한다.