쉬운 문자열 문제

정수 $N$과 문자열 $S_1,S_2,\ldots,S_K$가 주어진다.

당신은 알파벳 소문자로만 이루어진 길이가 정확히 $N$인 문자열 $T$를 만들어야 한다.

각 $i$에 대해 $S_i$가 $T$의 부분 문자열(substring)로 한 번 등장할 때마다 $1$점을 얻는다. 같은 $S_i$가 여러 위치에서 등장하면 등장한 횟수만큼 점수를 얻는다. 또한 서로 다른 $i,j$에 대해 $S_i=S_j$일 수 있으며, 이 경우 두 문자열은 따로 점수에 기여한다.

얻을 수 있는 점수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $K$ $S_1$ $S_2$ $\vdots$ $S_K$

얻을 수 있는 점수의 최댓값을 출력한다.

• $1 \le N \le 10^9$
• $1 \le K \le 500$
• $1 \le |S_i|$
• $\sum_{i=1}^{K}|S_i| \le 500$
• $S_i$는 알파벳 소문자로만 이루어져 있다.
• 모든 입력값은 정수이거나 문자열이다.