Problem L
Scrabble Flash
Players of this game have noticed that it is much easier to find another word that is similar to the current word than to find another word that is less similar. These players believe they have come up with a formula to estimate the amount of time it takes to find the next word given the word you have most recently found. Let $w$ be the length of the the word being found, and $s$ be the length of the longest common substring of the two words. They estimate that it takes a person
\[ \frac{w (w+1)}{2} - \frac{s(s+1)}{2} \]seconds to find the next word.
Given a list of words, they would like you to 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$). Following this are $N$ lines, each with one word consisting of 1–5 lowercase letters a–z. The first word is the word you start with, and is considered found at 0 seconds. All $N$ words are distinct.
Output
Print a single number that is the maximum number of words you can find in the given number of seconds.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 4 five four jive dive |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 4 une deux rouge bleue |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 4 five four jive dive |
4 |
