The longer the code, the stronger the code. The power number (P) of a code determines the strength of a code.

While computing the power number of a code we should ignore the keywords in the code. A few sample key words would be int, unsigned, string, etc. The power of a code can be determined by the number of characters in the code that do not belong to any of the keywords.

More formally, for each keyword K, consider all the occurrences of K in the code, ignore all these matching substrings while computing the power. See the example for clarity.

Example: 

If you take a code to be

int main() { mlinteger a; return 0; }

The above code has 37 characters in total.

If the key words are

int
return
lint
integer

Then the power of the above code would be 20, spaces need to be counted:

" main() { "   --> 10
"m a; "         --> 5
" 0; }"        --> 5

The codes can be concatenated to be made more powerful. If we have two codes C1, C2 with power P1, P2, the power of code C1 $C2**(here**$ denotes concatenation) will be P1 + P2.

While concatenating two codes, a % character gets inseted in between the two codes. For example if C1 was print 5; and C2 was print 6;, C1 $ C2 = print 5;%print 6;

You are given N codes, K keywords, you can use each code as many number of times as you want. You are to output the largest power X, that can't be attained by concatinating the codes.

Note:

All the following operations are possible.

Two same codes can be concatenated with each other.
Some codes need not be used in the concatenation.
Each code can be used any number of times.

Input Format 

First line contains N. In the following N lines, the i^{th} line represents the code C_{i}. The following line contains K the number of keywords. The following K lines one keyword each.

Output Format 

Print a single line containing X as described above.

Constraints

1 <= N <= 10
1 <= |C_i| <= 100000
1 <= K <= 100
1 <= each keyword length <= 1000

Note:

Key words do not contain spaces. Both the code and the key words do not contain % character. They can contain any other ASCII character.
If the answer is infinite then print -1.

Sample Input: #1

5
lint maint lllint
int maint lllintl
lint maint lllint
lint maint lllint
lint maint lllint
2
int
lint

Sample Output: #1

29

Sample Input: #2

3
ababaac
babab
abcbab
1
bab

Sample Output: #2

5

Explanation:

In sample 1, the powers of codes are 6, 7, 6, 6. And hence the maximum unattainable power by combination is 29. In sample 2, the powers are 4, 0, 3, and hence the result is 5.

Source: hackerrank | Difficulty: HARD
Tags: Combinatorics


Solutions:
import sys, math, re
from collections import defaultdict, deque
testing = [False]

def build_match_remover(subs):
	subs2 = []
	charToRep = {}
	for kw in subs:
		kwchars = set(kw)
		if len(kwchars) == 1:
			k = charToRep.get(kw[0])
			charToRep[kw[0]] = len(kw) if k is None else min(len(kw), k)
		else:
			subs2.append([kw, kwchars, None])
	for (c, k) in charToRep.items():
		subs2.append([c * k, {c}, None])
	subs = subs2
	subs.sort(key=lambda x: len(x[0]), reverse=True)
	for sub in subs:
		clause = re.escape(sub[0])
		sub[2] = re.compile('(?=({}))'.format(clause))

	def process(code):
		n = len(code)
		chars = set(code)
		exclude = [False] * n
		imin = 0
		for (ipat, sub) in enumerate(subs):
			if not sub[1] <= chars:
				continue
			(kw, pat) = (sub[0], sub[2])
			lastMatchEnd = 0
			istart = max(0, imin - len(kw))
			for match in pat.finditer(code[istart:]):
				(i1, i2) = (max(lastMatchEnd, match.start(1)), match.end(1))
				exclude[istart + i1:istart + i2] = [True] * (i2 - i1)
				lastMatchEnd = i2 - 1
			while imin < n and exclude[imin]:
				imin += 1
			if imin == n:
				break
		return ''.join([c for (i, c) in enumerate(code) if exclude[i] == False])
	return process

def remove_matches(process, srcs):
	return [process(s) for s in srcs]

def test_remove_matches():
	print('Testing remove_matches')
	for (srcs, subs, eans) in [[['11110111101111101110'], ['111', '11110'], ['0']]]:
		remover = build_match_remover(subs)
		ans = remove_matches(remover, srcs)
		if ans != eans:
			print('FAIL: {}: {}/{}: Expected {}, got {}'.format('remove matches', srcs, subs, eans, ans))

def test_frobenius(frobenius):
	for (a, eans) in [[[3, 5], 7], [[6, 9, 20], 43], [[66488, 66613, 66643, 66669, 66670, 66673, 66768, 66782, 66806, 66860], 12168243]]:
		ans = frobenius(a)
		if ans != eans:
			print('FAIL: {}: {}: Expected {}, got {}'.format(frobenius.__name__, a, eans, ans))

def frobenius_rr(a):
	a.sort()
	k = len(a)
	a1 = a[0]
	n = [0] + [math.inf] * (a1 - 1)
	for i in range(1, k):
		d = math.gcd(a1, a[i])
		for r in range(0, d):
			nmin = min([n[q] for q in range(r, r + a1, d)])
			if nmin < math.inf:
				for _ in range(a1 // d):
					nmin = nmin + a[i]
					p = nmin % a1
					nmin = min(nmin, n[p])
					n[p] = nmin
	return max(n) - a1

def frobenius_bfd(a):
	a.sort()
	n = len(a)
	a1 = a[0]
	(Q, Qset) = (deque(), set())
	Q.append(0)
	Qset.add(0)
	P = [n - 1] * a1
	S = [0] + [a[0] * a[n - 1]] * (a1 - 1)
	Amod = [x % a1 for x in a]
	while Q:
		v = Q.popleft()
		Qset.remove(v)
		for j in range(1, P[v] + 1):
			u = v + Amod[j]
			if u >= a1:
				u -= a1
			w = S[v] + a[j]
			if w == S[u]:
				if j < P[u]:
					P[u] = j
			elif w < S[u]:
				S[u] = w
				P[u] = j
				if u not in Qset:
					Q.append(u)
					Qset.add(u)
	return max(S) - a1

def frobenius_dqqd(a):
	pass

def answer(codes, keywords):
	codes = set(codes)
	remover = build_match_remover(keywords)
	lens = []
	g = None
	for code in codes:
		code = remover(code)
		k = len(code)
		if k == 0:
			continue
		if k == 1:
			return 0
		g = math.gcd(g, k) if g is not None else k
		lens.append(k)
	if not lens or g != 1:
		return -1
	lens.sort()
	if testing[0]:
		print('Removed substrings', file=sys.stderr)
	return frobenius_rr(lens)

def main():
	if len(sys.argv) >= 2 and sys.argv[1] == '--test':
		testing[0] = True
		for f in [frobenius_bfd, frobenius_rr]:
			print('Testing {}'.format(f.__name__))
			test_frobenius(f)
		test_remove_matches()
	ncodes = int(sys.stdin.readline())
	codes = [sys.stdin.readline().strip() for _ in range(ncodes)]
	nkeywords = int(sys.stdin.readline())
	keywords = [sys.stdin.readline().strip() for _ in range(nkeywords)]
	if testing[0]:
		print('Read input', file=sys.stderr)
	print(answer(codes, keywords))
main()


import sys, math, re
from collections import defaultdict, deque
testing = [False]

def build_match_remover(subs):
	subs2 = []
	charToRep = {}
	for kw in subs:
		kwchars = set(kw)
		if len(kwchars) == 1:
			k = charToRep.get(kw[0])
			charToRep[kw[0]] = len(kw) if k is None else min(len(kw), k)
		else:
			subs2.append([kw, kwchars, None])
	for (c, k) in charToRep.items():
		subs2.append([c * k, {c}, None])
	subs = subs2
	subs.sort(key=lambda x: len(x[0]), reverse=True)
	for sub in subs:
		clause = re.escape(sub[0])
		sub[2] = re.compile('(?=({}))'.format(clause))

	def process(code):
		n = len(code)
		chars = set(code)
		exclude = [False] * n
		imin = 0
		for (ipat, sub) in enumerate(subs):
			if not sub[1] <= chars:
				continue
			(kw, pat) = (sub[0], sub[2])
			lastMatchEnd = 0
			istart = max(0, imin - len(kw))
			for match in pat.finditer(code[istart:]):
				(i1, i2) = (max(lastMatchEnd, match.start(1)), match.end(1))
				exclude[istart + i1:istart + i2] = [True] * (i2 - i1)
				lastMatchEnd = i2 - 1
			while imin < n and exclude[imin]:
				imin += 1
			if imin == n:
				break
		return ''.join([c for (i, c) in enumerate(code) if exclude[i] == False])
	return process

def remove_matches(process, srcs):
	return [process(s) for s in srcs]

def test_remove_matches():
	print('Testing remove_matches')
	for (srcs, subs, eans) in [[['11110111101111101110'], ['111', '11110'], ['0']]]:
		remover = build_match_remover(subs)
		ans = remove_matches(remover, srcs)
		if ans != eans:
			print('FAIL: {}: {}/{}: Expected {}, got {}'.format('remove matches', srcs, subs, eans, ans))

def test_frobenius(frobenius):
	for (a, eans) in [[[3, 5], 7], [[6, 9, 20], 43], [[66488, 66613, 66643, 66669, 66670, 66673, 66768, 66782, 66806, 66860], 12168243]]:
		ans = frobenius(a)
		if ans != eans:
			print('FAIL: {}: {}: Expected {}, got {}'.format(frobenius.__name__, a, eans, ans))

def frobenius_rr(a):
	a.sort()
	k = len(a)
	a1 = a[0]
	n = [0] + [math.inf] * (a1 - 1)
	for i in range(1, k):
		d = math.gcd(a1, a[i])
		for r in range(0, d):
			nmin = min([n[q] for q in range(r, r + a1, d)])
			if nmin < math.inf:
				for _ in range(a1 // d):
					nmin = nmin + a[i]
					p = nmin % a1
					nmin = min(nmin, n[p])
					n[p] = nmin
	return max(n) - a1

def frobenius_bfd(a):
	a.sort()
	n = len(a)
	a1 = a[0]
	(Q, Qset) = (deque(), set())
	Q.append(0)
	Qset.add(0)
	P = [n - 1] * a1
	S = [0] + [a[0] * a[n - 1]] * (a1 - 1)
	Amod = [x % a1 for x in a]
	while Q:
		v = Q.popleft()
		Qset.remove(v)
		for j in range(1, P[v] + 1):
			u = v + Amod[j]
			if u >= a1:
				u -= a1
			w = S[v] + a[j]
			if w == S[u]:
				if j < P[u]:
					P[u] = j
			elif w < S[u]:
				S[u] = w
				P[u] = j
				if u not in Qset:
					Q.append(u)
					Qset.add(u)
	return max(S) - a1

def frobenius_dqqd(a):
	pass

def answer(codes, keywords):
	codes = set(codes)
	remover = build_match_remover(keywords)
	lens = []
	g = None
	for code in codes:
		code = remover(code)
		k = len(code)
		if k == 0:
			continue
		if k == 1:
			return 0
		g = math.gcd(g, k) if g is not None else k
		lens.append(k)
	if not lens or g != 1:
		return -1
	lens.sort()
	if testing[0]:
		print('Removed substrings', file=sys.stderr)
	return frobenius_rr(lens)

def main():
	if len(sys.argv) >= 2 and sys.argv[1] == '--test':
		testing[0] = True
		for f in [frobenius_bfd, frobenius_rr]:
			print('Testing {}'.format(f.__name__))
			test_frobenius(f)
		test_remove_matches()
	ncodes = int(sys.stdin.readline())
	codes = [sys.stdin.readline().strip() for _ in range(ncodes)]
	nkeywords = int(sys.stdin.readline())
	keywords = [sys.stdin.readline().strip() for _ in range(nkeywords)]
	if testing[0]:
		print('Read input', file=sys.stderr)
	print(answer(codes, keywords))
main()