#349 strings

Loading problem...

Preparing the statement, recent submissions, and submit form.

#349 strings | DOJ

DOJ/Beginner Contest DOJ/BCD 4

Authors: lunarlity

Time limit: 4000 ms
Memory limit: 1024 MB
Checker: DIFF
Solve threshold: 100

Statement

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

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

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

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

부분 문자열(substring)의 정의

문자열 $X$ 가 문자열 $T$ 의 부분 문자열로 등장한다는 것은, 어떤 정수 $l,r$ 이 존재하여 $1 \le l \le r \le |T|$ , $r-l+1=|X|$ 이고

T_lT_{l+1}\cdots T_r=X

를 만족한다는 뜻이다.

즉, $T$ 의 연속한 몇 개의 문자로 이루어진 문자열이 $X$ 와 같으면 $X$ 가 $T$ 의 부분 문자열로 등장한다고 한다.

Input

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

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

Output

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

Constraints

$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$ 는 알파벳 소문자로만 이루어져 있다.
모든 입력값은 정수이거나 문자열이다.

Subtasks

#	Score	Constraints
1	7	$1 \le N \le 20$ $\sum_{i=1}^{K}\|S_i\| \le 20$
2	17	$1 \le N \le 500$ $\sum_{i=1}^{K}\|S_i\| \le 60$
3	21	$\sum_{i=1}^{K}\|S_i\| \le 80$
4	24	$1 \le N \le 20\,000$
5	31	추가 제약이 없다.

Samples

Sample 1

Input

5 2
a
aa

Output

Sample 2

Input

6 3
ab
ba
aba

Output

Editorial

View editorial

쉬운 문자열 문제

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial