You are given a text consisting of $n$ space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. $w_i$ is the $i$-th word of text. All words consist only of lowercase Latin letters.

Let's denote a segment of words $w[i..j]$ as a sequence of words $w_i, w_{i + 1}, \dots, w_j$. Two segments of words $w[i_1 .. j_1]$ and $w[i_2 .. j_2]$ are considered equal if $j_1 - i_1 = j_2 - i_2$, $j_1 \ge i_1$, $j_2 \ge i_2$, and for every $t \in [0, j_1 - i_1]$ $w_{i_1 + t} = w_{i_2 + t}$. For example, for the text "to be or not to be" the segments $w[1..2]$ and $w[5..6]$ are equal, they correspond to the words "to be".

An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text "a ab a a b ab a a b c" you can replace segments of words $w[2..4]$ and $w[6..8]$ with an abbreviation "AAA" and obtain the text "a AAA b AAA b c", or you can replace segments of words $w[2..5]$ and $w[6..9]$ with an abbreviation "AAAB" and obtain the text "a AAAB AAAB c".

What is the minimum length of the text after at most one abbreviation?


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 300$) — the number of words in the text.

The next line contains $n$ space-separated words of the text $w_1, w_2, \dots, w_n$. Each word consists only of lowercase Latin letters.

It is guaranteed that the length of text does not exceed $10^5$.


-----Output-----

Print one integer — the minimum length of the text after at most one abbreviation.


-----Examples-----
Input
6
to be or not to be

Output
12

Input
10
a ab a a b ab a a b c

Output
13

Input
6
aa bb aa aa bb bb

Output
11



-----Note-----

In the first example you can obtain the text "TB or not TB".

In the second example you can obtain the text "a AAAB AAAB c".

In the third example you can obtain the text "AB aa AB bb".

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Dynamic programming


Solutions:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
a = list(s.split())
eq = [[0 for i in range(n)] for j in range(n)]
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	eq[i][i] = 1
	for j in range(0, i):
		if a[i] == a[j]:
			eq[i][j] += 1
			eq[j][i] += 1
for i in range(n - 1, -1, -1):
	for j in range(n - 1, -1, -1):
		if eq[i][j] == 1:
			if i < n - 1 and j < n - 1:
				dp[i][j] = dp[i + 1][j + 1] + 1
			else:
				dp[i][j] = 1
allsum = n - 1
for k in a:
	allsum += len(k)
ans = allsum
for i in range(n):
	sx = 0
	j = 0
	while i + j < n:
		sx += len(a[i + j])
		cnt = 1
		pos = i + j + 1
		while pos < n:
			if dp[i][pos] > j:
				cnt += 1
				pos += j
			pos += 1
		cur = allsum - sx * cnt + (j + 1) * cnt - j * cnt
		if cnt > 1 and ans > cur:
			ans = cur
		j += 1
print(ans)


N = 303
eq = []
dp = []
for i in range(N):
	eq.append([False] * N)
for i in range(N):
	dp.append([0] * N)
n = int(input())
s = input()
allsum = len(s)
s = s.split()
for i in range(n):
	eq[i][i] = True
	for j in range(i):
		eq[i][j] = eq[j][i] = s[i] == s[j]
for i in range(n - 1, -1, -1):
	for j in range(n - 1, -1, -1):
		if eq[i][j]:
			if i < n - 1 and j < n - 1:
				dp[i][j] = dp[i + 1][j + 1] + 1
			else:
				dp[i][j] = 1
ans = allsum
for i in range(n):
	su = 0
	for j in range(n - i):
		su += len(s[i + j])
		cnt = 1
		pos = i + j + 1
		while pos < n:
			if dp[i][pos] > j:
				cnt += 1
				pos += j
			pos += 1
		cur = allsum - su * cnt + (j + 1) * cnt - j * cnt
		if cnt > 1 and ans > cur:
			ans = cur
print(ans)


from sys import stdin

def kmp(pat, txt):
	leng = 0
	i = 1
	ans = 0
	M = len(pat)
	N = len(txt)
	lps = [0] * M
	j = 0
	while i < M:
		if pat[i] == pat[leng]:
			leng += 1
			lps[i] = leng
			i += 1
		elif leng != 0:
			leng = lps[leng - 1]
		else:
			lps[i] = 0
			i += 1
	i = 0
	while i < N:
		if pat[j] == txt[i]:
			i += 1
			j += 1
		if j == M:
			if (i - j == 0 or txt[i - j - 1] == ' ') and (i - j + len(pat) == len(txt) or txt[i - j + len(pat)] == ' '):
				ans += 1
				i = i - j + len(pat)
				j = 0
			else:
				j = lps[j - 1]
		elif i < N and pat[j] != txt[i]:
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	return ans
n = int(stdin.readline().strip())
s1 = stdin.readline().strip().split()
s = []
x = 1
d = dict()
d1 = dict()
st = set()
ans = n - 1
s2 = ''
for i in s1:
	ans += len(i)
	if i not in st:
		d.update({i: x})
		d1.update({x: len(i)})
		x += 1
		st.add(i)
	s.append(d[i])
	s2 += str(d[i])
	if len(s) < n:
		s2 += ' '
acum = 0
s3 = s2.split()
tot = ans
for i in range(n):
	x = 0
	y = 0
	for j in range(i, n):
		x += d1[s[j]] - 1
		y += len(s3[j])
		z = kmp(s2[acum:acum + y + j - i], s2)
		if z > 1:
			aux = tot - z * (x + j - i)
			if aux < ans:
				ans = aux
	acum += len(s3[i]) + 1
print(ans)


import math
from collections import defaultdict

def main():
	p = 31
	m = 1000000000.0 + 9

	def string_hash(s):
		hash_value = 0
		p_pow = 1
		for c in s:
			hash_value = (hash_value + (ord(c) - ord('a') + 1) * p_pow) % m
			p_pow = p_pow * p % m
		return hash_value
	n = int(input())
	words = input().split()
	eq = [[False] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				eq[i][j] = eq[j][i] = True
			else:
				eq[i][j] = eq[i][j] = words[i] == words[j]
	dp = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if not eq[i][j]:
				dp[i][j] = 0
			elif i < n - 1 and j < n - 1:
				dp[i][j] = dp[i + 1][j + 1] + 1
			else:
				dp[i][j] = 1
	all = sum((len(w) for w in words)) + n - 1
	ans = all
	for start in range(n):
		size = 1
		while start + size < n:
			num = 1
			pos = start + size
			while pos + size <= n:
				if dp[start][pos] >= size:
					num += 1
					pos += size
				else:
					pos += 1
			if num > 1:
				segsize = sum((len(words[i]) for i in range(start, start + size))) + size - 1
				newsize = size
				ans = min(ans, all - num * segsize + num * newsize)
			size += 1
	print(ans)
main()


n = int(input())
arr = input()
final = len(arr)
arr = arr.split()
lens = [0 for x in range(n)]
visit = [0 for x in range(n)]
cnt = 0
ans = 0
for i in range(n):
	if visit[i]:
		continue
	lens[cnt] = len(arr[i])
	for j in range(i + 1, n):
		if arr[j] == arr[i]:
			arr[j] = cnt
			visit[j] = 1
	arr[i] = cnt
	cnt += 1
for i in range(n):
	for j in range(i, n):
		temp = arr[i:j + 1]
		ind = 1
		found = 0
		len2 = j - i + 1
		cur = 0
		kmp = [0 for x in range(len2)]
		while ind < len2:
			if temp[ind] == temp[cur]:
				cur += 1
				kmp[ind] = cur
				ind += 1
			elif cur != 0:
				cur -= 1
			else:
				kmp[ind] = 0
				ind += 1
		ind = 0
		cur = 0
		while ind < n:
			if arr[ind] == temp[cur]:
				ind += 1
				cur += 1
			if cur == len2:
				found += 1
				cur = 0
			elif ind < n and temp[cur] != arr[ind]:
				if cur != 0:
					cur = kmp[cur - 1]
				else:
					ind += 1
		if found > 1:
			res = 0
			for k in temp:
				res += (lens[k] - 1) * found
			res += (len(temp) - 1) * found
			ans = max(ans, res)
print(final - ans)