Scrabble Flash

Time limit4sMemory limit1024 MB

Summary

Find the most words you can chain from a start word within U seconds, where each step's cost depends on the longest common substring with the previous word.

Level: Medium5 of 10
Topics: Dynamic programming, Bit manipulation, String
Solved: No attempts yet

Problem

In the game of Scrabble Flash, you are given 5 tiles of letters, and you want to find as many words as you can before time runs out. In this version, pressing a button changes the letter on a tile to any other letter you choose. Changing letters takes time, so you should avoid changes as much as possible.

Players have noticed that it is much easier to find a word similar to the current word than a word that is less similar. Players estimate the time needed to find the next word from the most recently found word. Let $w$ be the length of the word being found, and $s$ be the length of the longest common substring of the two words. The estimated time, in seconds, is

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

Given a list of words, find the maximum number of words that can be found in a given number of seconds.

Input

The first line contains two space-separated integers: $U$ , the number of seconds, and $N$ , the number of words to consider ( $0 \leq U \leq 100$ , $1 \leq N \leq 10$ ). Then $N$ lines follow, each with one word of 1 to 5 lowercase letters a to z. The first word is the word you start with, and it is considered found at 0 seconds. All $N$ words are distinct.

Output

Print a single number: the maximum number of words you can find in the given number of seconds.

Examples3

Example 1
Input
```
8 4
five
four
jive
dive
```
Expected output
```
3
```
Example 2
Input
```
5 4
une
deux
rouge
bleue
```
Expected output
```
1
```
Example 3
Input
```
20 4
five
four
jive
dive
```
Expected output
```
4
```