Greg wants to build a string, $\mbox{S}$ of length $N$. Starting with an empty string, he can perform $2$ operations:

Add a character to the end of $\mbox{S}$ for $\mbox{A}$ dollars.

Copy any substring of $\mbox{S}$, and then add it to the end of $\mbox{S}$ for $\mbox{B}$ dollars.

Calculate minimum amount of money Greg needs to build $\mbox{S}$.

Input Format

The first line contains number of testcases $\mathbf{T}$.        

The $2\times T$ subsequent lines each describe a test case over $2$ lines: 

The first contains $3$ space-separated integers, $N$, $\mbox{A}$ , and $\mbox{B}$, respectively. 

The second contains $\mbox{S}$ (the string Greg wishes to build).

Constraints

$1\leq T\leq3$
$1\leq N\leq3\times10^4$
$1\leq A,B\leq10000$
$\mbox{S}$ is composed of lowercase letters only.

Output Format

On a single line for each test case, print the minimum cost (as an integer) to build $\mbox{S}$.

Sample Input
2
9 4 5
aabaacaba
9 8 9
bacbacacb

Sample Output
26
42

Explanation

Test Case 0: 

$S_{initial}=$ ""; $S_{final}=$ "$aaba aaba$" 

Append "$a$"; $S=$ "$a$"; cost is $4$ 

Append "$a$"; $S=$ "$aa$"; cost is $4$ 

Append "$\boldsymbol{b}$"; $S=$ "$\textit{aab}$"; cost is $4$ 

Copy and append "$\boldsymbol{a}\boldsymbol{a}$"; $S=$ "$a abaa$"; cost is $5$ 

Append "$\textbf{C}$"; $S=$ "$a a b a c$"; cost is $4$ 

Copy and append "$\boldsymbol{aba}$"; $S=$ "$aaba aaba$"; cost is $5$        

Summing each cost, we get $4+4+4+5+4+5=26$, so our output for Test Case 1 is $26$.

Test Case 1: 

$S_{initial}=$ ""; $S_{final}=$ "$bacbacacb$" 

Append "$\boldsymbol{b}$"; $S=$ "$\boldsymbol{b}$"; cost is $8$ 

Append "$\boldsymbol{\alpha}$"; $S=$ "$\textbf{ba}$"; cost is $8$ 

Append "$\textbf{C}$"; $S=$ "$\textbf{bac}$"; cost is $8$ 

Copy and append "$\textbf{bac}$"; $S=$ "$bacbac$"; cost is $9$ 

Copy and append "$\boldsymbol{acb}$"; $S=$ "$bacbacacb$"; cost is $9$

Summing each cost, we get $8+8+8+9+9=42$, so our output for Test Case 2 is $\textbf{42}$.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Starter code:

Solutions:
rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


samples_size = int(input())
for idx in range(samples_size):
	(N, A, B) = [int(ss) for ss in input().split()]
	_str = input()
	assert N == len(_str)
	_s = _str[::-1]
	cost = pos = 0
	s = ''

	def calc_cost(l):
		return B if l > 1 else A

	def find_part_size(start_pos):
		size = 0
		sle = ('', '')
		while True:
			size += 1
			s = (_s[start_pos:start_pos + size + 1], _s[start_pos + size + 1:])
			if s[1].find(s[0]) == -1:
				break
			sle = s
		return (size, sle)
	while pos < N:
		flag = False
		(size, sle) = find_part_size(pos)
		if size > 1:
			(nsize, nsle) = find_part_size(pos + size)
			(dsize, dsle) = find_part_size(pos + 1)
			nl = size + nsize
			dl = 1 + dsize
			dcost = calc_cost(1) + calc_cost(dsize)
			ncost = calc_cost(size) + calc_cost(nsize)
			while True:
				if nl >= dl and ncost <= dcost:
					flag = True
					break
				elif nl <= dl and ncost >= dcost:
					flag = False
					break
				elif nl <= dl and ncost < dcost:
					(nlen, _) = find_part_size(pos + nl)
					ncost += calc_cost(nlen)
					nl += nlen
				elif nl > dl and ncost > dcost:
					(dlen, _) = find_part_size(pos + dl)
					dcost += calc_cost(dlen)
					dl += dlen
				else:
					raise RuntimeError('unexpected')
		if flag:
			s += _s[pos:pos + size]
			pos += size
			cost += B
		else:
			s += _s[pos:pos + 1]
			pos += 1
			cost += A
	s = s[::-1]
	assert s == _str
	print(cost)


def get_costs(line, N, A, B):
	costs = [-1 for i in range(N)]
	costs[0] = A
	prev_i = 1
	for j in range(1, N):
		costs[j] = costs[j - 1] + A
		i = j
		if line[prev_i:j + 1] in line[:prev_i]:
			costs[j] = min([costs[j], costs[prev_i - 1] + B])
		else:
			prev_i = j + 1
			while i > j / 2 and line[i:j + 1] in line[:i]:
				costs[j] = min([costs[j], costs[i - 1] + B])
				prev_i = i
				i -= 1
	return costs[N - 1]
T = int(input())
for t in range(T):
	(N, A, B) = [int(x) for x in input().strip().split(' ')]
	line = input().strip()
	print(get_costs(line, N, A, B))


def solve(N, A, B, S):
	d = dict()
	d[S[0]] = A
	k = 0
	if N * A < B:
		return N * A
	for i in range(1, N):
		test = ''
		testword = S[:i]
		prix = d[testword]
		j = k + 1
		test += S[i:j + 1]
		while test in testword and j < N - 1:
			j += 1
			test += S[j]
		k = j - 1
		if test not in testword:
			test = test[:-1]
		if len(test) * A > B:
			newword = testword + test
			newprice = prix + B
			if newword not in d.keys():
				d[newword] = newprice
			else:
				d[newword] = min(d[newword], newprice)
		if B > A or test != []:
			newword = testword + S[i]
			newprice = prix + A
			if newword not in d.keys():
				d[newword] = newprice
			else:
				d[newword] = min(d[newword], newprice)
	return d[S]
T = int(input())
for i in range(T):
	L = list(map(int, input().strip().split(' ')))
	N = L[0]
	A = L[1]
	B = L[2]
	S = input()
	result = solve(N, A, B, S)
	print(result)


def calcCost(s, a, b):
	len_s = len(s)
	min_len_4copy = b // a + (1 if b % a else 0)
	min_lens_4copy = [min_len_4copy] * len_s
	costs = [max(a, b) * len_s] * len_s
	curr_cost = 0
	booster = {}
	if min_len_4copy < 3:
		for i in range(len_s - 2, -1, -1):
			booster[s[i:i + 2]] = i
	if min_len_4copy < 2:
		for i in range(len_s - 1, -1, -1):
			booster[s[i:i + 1]] = i
	for i in range(len_s):
		max_len4c = 0
		min_len4c = min_lens_4copy[i]
		pos = 0
		for len4c in range(min_len4c, min(i, len_s - i) + 1):
			to_search = s[i:i + len4c]
			if len4c < 3:
				pos = booster[to_search] if to_search in booster else -1
				if pos > i - len4c:
					pos = -1
			else:
				pos = s.find(to_search, pos, i)
			if pos >= 0:
				max_len4c = len4c
			else:
				break
		if max_len4c:
			for len4c in range(min_len4c, max_len4c + 1):
				ci = i + len4c - 1
				costs[ci] = min(costs[ci], curr_cost + b)
				min_lens_4copy[ci] = max(min_lens_4copy[ci], max_len4c - len4c)
		costs[i] = min(costs[i], curr_cost + a)
		curr_cost = costs[i]
	return costs[len_s - 1]
t = int(input())
results = []
for i in range(t):
	(n, a, b) = input().strip().split(' ')
	(n, a, b) = [int(n), int(a), int(b)]
	s = input()
	results.append(calcCost(s, a, b))
for res in results:
	print(res)


import sys
from typing import List

class Suffix(object):

	def __init__(self, index: int, rank: int, next_rank: int):
		self.index = index
		self.rank = rank
		self.next_rank = next_rank

	def __cmp__(self, other):
		if self.rank == other.rank:
			return self.next_rank - other.next_rank
		else:
			return self.rank - other.rank

	def __lt__(self, other):
		return self.__cmp__(other) < 0

class SuffixArrayBuilder(object):

	@staticmethod
	def build(text):
		text_len = len(text)
		suffixes = [Suffix(i, ord(text[i]) - ord('a'), ord(text[i + 1]) - ord('a') if i + 1 < text_len else -1) for i in range(0, text_len)]
		suffixes.sort()
		ind = [0 for _ in range(0, text_len)]
		k = 4
		while k < 2 * text_len:
			rank = 0
			prev_rank = suffixes[0].rank
			suffixes[0].rank = rank
			ind[suffixes[0].index] = 0
			for i in range(1, text_len):
				if suffixes[i].rank != prev_rank or suffixes[i].next_rank != suffixes[i - 1].next_rank:
					rank += 1
				prev_rank = suffixes[i].rank
				suffixes[i].rank = rank
				ind[suffixes[i].index] = i
			for i in range(0, text_len):
				next_index = suffixes[i].index + k // 2
				suffixes[i].next_rank = suffixes[ind[next_index]].rank if next_index < text_len else -1
			suffixes.sort()
			k *= 2
		return [s.index for s in suffixes]

	@staticmethod
	def inverse(suffixes: List[int]):
		inv_suffixes = [0 for _ in range(0, len(suffixes))]
		for i in range(0, len(suffixes)):
			inv_suffixes[suffixes[i]] = i
		return inv_suffixes

class LCPArrayBuilder(object):

	@staticmethod
	def build(text: str, suffixes: List[int], inv_suffixes: List[int]):
		text_len = len(text)
		lcp = [0 for _ in range(0, text_len)]
		k = 0
		for i in range(0, text_len):
			if inv_suffixes[i] == text_len - 1:
				k = 0
				continue
			j = suffixes[inv_suffixes[i] + 1]
			while i + k < text_len and j + k < text_len and (text[i + k] == text[j + k]):
				k += 1
			lcp[inv_suffixes[i]] = k
			if k > 0:
				k -= 1
		return lcp

def find_longest_substring(start_prefix: int, suffixes: List[int], inv_suffixes: List[int], lcp: List[int]):
	best_left = traverse_suffixes(start_prefix, suffixes, inv_suffixes, lcp, True)
	best_right = traverse_suffixes(start_prefix, suffixes, inv_suffixes, lcp, False)
	return max(best_left, best_right)

def traverse_suffixes(start_prefix: int, suffixes: List[int], inv_suffixes: List[int], lcp: List[int], go_left: bool):
	text_len = len(suffixes)
	start_prefix_order = inv_suffixes[start_prefix]
	current_prefix_order = start_prefix_order - 1 if go_left else start_prefix_order
	max_allowed_lcp = text_len
	best_length = 0
	while 0 <= current_prefix_order < text_len - 1 and max_allowed_lcp > 0:
		max_allowed_lcp = min(max_allowed_lcp, lcp[current_prefix_order])
		current_prefix = suffixes[current_prefix_order if go_left else current_prefix_order + 1]
		if start_prefix >= current_prefix:
			amended_lcp_value = min(max_allowed_lcp, start_prefix - current_prefix)
			best_length = max(best_length, amended_lcp_value)
			if best_length >= max_allowed_lcp or start_prefix + best_length >= text_len - 1:
				break
		if go_left:
			current_prefix_order -= 1
		else:
			current_prefix_order += 1
	return best_length

def solve_single_test_case(text, append_cost, substring_cost):
	best_costs = [sys.maxsize for _ in range(len(text) + 1)]
	best_costs[0] = 0
	best_costs[1] = append_cost
	suffixes = SuffixArrayBuilder.build(text)
	inv_suffixes = SuffixArrayBuilder.inverse(suffixes)
	lcp = LCPArrayBuilder.build(text, suffixes, inv_suffixes)
	for i in range(1, len(text)):
		longest_substring_length = find_longest_substring(i, suffixes, inv_suffixes, lcp)
		current_best_cost = best_costs[i]
		for j in range(longest_substring_length, 0, -1):
			if best_costs[i + j] > current_best_cost + substring_cost:
				best_costs[i + j] = current_best_cost + substring_cost
			else:
				break
		if i + 1 <= len(text):
			if best_costs[i + 1] > current_best_cost + append_cost:
				best_costs[i + 1] = current_best_cost + append_cost
	print(best_costs[len(text)])

def solve_all_test_cases():
	n_of_test_cases = int(input())
	for _ in range(n_of_test_cases):
		(_, append_cost, substring_cost) = tuple([int(x) for x in input().split()])
		text = input()
		solve_single_test_case(text, append_cost, substring_cost)

def solve_all_test_cases_from_file():
	with open(sys.argv[1]) as txt:
		n_of_test_cases = int(txt.readline())
		for _ in range(n_of_test_cases):
			(_, append_cost, substring_cost) = tuple([int(x) for x in txt.readline().split()])
			text = txt.readline()[:-1]
			solve_single_test_case(text, append_cost, substring_cost)
solve_all_test_cases()


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


import os
import sys

def sol():
	(N, A, B) = map(int, input().strip().split())
	S = input().strip()
	res = [0] * N
	res[0] = A
	maxl = 0
	for i in range(1, N):
		minv = res[i - 1] + A
		(cp, idx, newl) = (False, i, 0)
		for k in range(maxl, -1, -1):
			if S[i - k:i + 1] in S[0:i - k]:
				(cp, idx, newl) = (True, i - k, k + 1)
				break
		if cp:
			minv = min(minv, res[idx - 1] + B)
		maxl = newl
		res[i] = minv
	print(res[-1])
T = int(input().strip())
for x in range(T):
	sol()


from itertools import zip_longest, islice
import heapq
import sys

def sorted_idx(items):
	unique = sorted(set(items))
	idx = dict(zip(unique, range(len(unique))))
	return [idx[v] for v in items]

def suffix_array(s):
	n = len(s)
	k = 1
	sa = sorted_idx(s)
	while max(sa) < n - 1:
		sa = sorted_idx([a * (n + 1) + b + 1 for (a, b) in zip_longest(sa, islice(sa, k, None), fillvalue=-1)])
		k <<= 1
	return sa

def lcp_sa(s):
	inv_sa = suffix_array(s)
	n = len(inv_sa)
	sa = [0] * n
	for i in range(n):
		sa[inv_sa[i]] = i
	lcp = [0] * n
	k = 0
	for i in range(n):
		if inv_sa[i] == n - 1:
			k = 0
			continue
		j = sa[inv_sa[i] + 1]
		while i + k < n and j + k < n and (s[i + k] == s[j + k]):
			k += 1
		lcp[inv_sa[i] + 1] = k
		if k > 0:
			k -= 1
	return (sa, inv_sa, lcp)

def solve(s, A, B):
	n = len(s)
	(sa, inv_sa, lcp) = lcp_sa(s)

	def dijkstra(src, dist):
		heap = [(0, src)]
		cost = {}
		cost[src] = 0
		while heap:
			current = heapq.heappop(heap)[1]
			if current == dist:
				return cost[dist]
			for (neigh, weight) in graph[current].items():
				new_cost = cost[current] + weight
				if neigh not in cost or new_cost < cost[neigh]:
					heapq.heappush(heap, (new_cost, neigh))
					cost[neigh] = new_cost

	def get_left(i):
		p = inv_sa[i]
		q = p
		l = lcp[q]
		while q >= 0 and sa[q] >= i:
			l = min(l, lcp[q])
			q -= 1
		if l == 0:
			return (0, -1)
		assert sa[q] < i, 'error at {}'.format(i)
		return (l, sa[q])

	def get_right(i):
		p = inv_sa[i]
		q = p
		if q + 1 >= len(lcp):
			return (0, -1)
		l = lcp[q + 1]
		while q + 1 < len(lcp) and sa[q] >= i:
			q += 1
			l = min(l, lcp[q])
		if sa[q] >= i or l == 0:
			return (0, -1)
		assert sa[q] < i, 'error at {}'.format(i)
		return (l, sa[q])

	def get_max_step_bf(i):
		j = i
		while j < n and s[i:j + 1] in s[:i]:
			j += 1
		return max(0, j - i)

	def get_max_step(i):
		j = pi[i][1]
		l = pi[i][0]
		best_step = min(l, i - j)
		while j >= 0 and l + j > i:
			best_step = max(best_step, i - j)
			l = min(l, pi[j][0])
			j = pi[j][1]
		if j == -1:
			return best_step
		return max(best_step, l)
	pi = [max([get_left(i), get_right(i)], key=lambda x: (x[0], -x[1])) for i in range(n)]
	graph = [dict() for _ in range(n)]

	def build_graph():
		for i in range(n):
			max_step = get_max_step(i)
			graph[i][i + 1] = A
			if max_step > 0 and B < A:
				graph[i][i + 1] = B
			if max_step >= 2:
				graph[i][i + max_step] = min(B, max_step * A)
	build_graph()
	return dijkstra(0, n)
t = int(input().strip())
for _ in range(t):
	(_, A, B) = map(int, input().strip().split())
	s = input().strip()
	print(solve(s, A, B))


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


import os
import sys

def buildString(a, b, s):
	bigSet = set()
	global lastFindResult

	def findinset(start, end):
		sSub = s[start:end]
		if sSub in bigSet:
			return True
		if s.find(sSub) <= start + start - end:
			if end - start < 8:
				bigSet.add(sSub)
			return True
		return False
	l = len(s)
	prices = list(range(l))
	prices[0] = a
	if a < b or s[1] != s[0]:
		prices[1] = a + a
	else:
		prices[1] = a + b
	lastFindResult = -1

	def testCaseI(j):
		global lastFindResult
		lastFindResult = s.find(s[j:i + 1])
		if lastFindResult <= j - (i + 1 - j):
			return True
		return False
	lastSuccesfulFindResult = (-1, 0)
	for i in range(2, l):
		copyStartMax = (i + 2) // 2
		successMinJ = i + 1
		unsuccessMaxJ = copyStartMax - 1
		foundBetter = False
		if lastSuccesfulFindResult[0] != -1:
			aLength = i + 1 - lastSuccesfulFindResult[1]
			if lastSuccesfulFindResult[1] > unsuccessMaxJ and lastSuccesfulFindResult[1] >= lastSuccesfulFindResult[0] + aLength:
				if s[lastSuccesfulFindResult[1]:i + 1] == s[lastSuccesfulFindResult[0]:lastSuccesfulFindResult[0] + aLength]:
					successMinJ = lastSuccesfulFindResult[1]
					foundBetter = True
		if not foundBetter:
			while successMinJ > unsuccessMaxJ + 1:
				jx = (successMinJ + unsuccessMaxJ + 1) // 2
				if testCaseI(jx):
					successMinJ = jx
					lastSuccesfulFindResult = (lastFindResult, jx)
				else:
					unsuccessMaxJ = jx
		if successMinJ < i:
			prices[i] = min(prices[successMinJ - 1] + b, prices[i - 1] + a)
		else:
			prices[i] = prices[i - 1] + a
			lastSuccesfulFindResult = (-1, 0)
	return prices[-1]
for t_itr in range(int(input())):
	nab = input().split()
	print(buildString(int(nab[1]), int(nab[2]), input()))


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


def get_costs(line, N, A, B):
	costs = [-1 for i in range(N)]
	costs[0] = A
	prev_i = 1
	for j in range(1, N):
		costs[j] = costs[j - 1] + A
		i = j
		if line[prev_i:j + 1] in line[:prev_i]:
			costs[j] = min([costs[j], costs[prev_i - 1] + B])
		else:
			prev_i = j + 1
			while i > j / 2 and line[i:j + 1] in line[:i]:
				costs[j] = min([costs[j], costs[i - 1] + B])
				prev_i = i
				i -= 1
	return costs[N - 1]
T = int(input())
for t in range(T):
	(N, A, B) = [int(x) for x in input().strip().split(' ')]
	line = input().strip()
	print(get_costs(line, N, A, B))


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


for case in range(int(input())):
	(N, a, r) = map(int, input().split())
	s = input()
	l = []
	lo = 0
	for hi in range(1, N + 1):
		while s[lo:hi] not in s[:lo]:
			lo += 1
		l.append(hi - lo)
	cost = [a]
	for i in range(1, N):
		if l[i] == 0:
			cost.append(cost[-1] + a)
		else:
			cost.append(min(cost[-1] + a, cost[i - l[i]] + r))
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


T = int(input())
for r in range(T):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


def buildstrings(n, a, b, s):
	d = dict()
	d[s[0]] = a
	k = 0
	if n * a < b:
		return n * a
	for i in range(1, n):
		test = ''
		testword = s[:i]
		prix = d[testword]
		j = k + 1
		test += s[i:j + 1]
		while test in testword and j < n - 1:
			j += 1
			test += s[j]
		k = j - 1
		if test not in testword:
			test = test[:-1]
		if len(test) * a > b:
			newword = testword + test
			newprice = prix + b
			if newword not in d.keys():
				d[newword] = newprice
			else:
				d[newword] = min(d[newword], newprice)
		if b > a or test != []:
			newword = testword + s[i]
			newprice = prix + a
			if newword not in d.keys():
				d[newword] = newprice
			else:
				d[newword] = min(d[newword], newprice)
	return d[s]
T = int(input())
for i in range(T):
	L = list(map(int, input().strip().split(' ')))
	n = L[0]
	a = L[1]
	b = L[2]
	s = input()
	result = buildstrings(n, a, b, s)
	print(result)


def solve():
	cost = [0 for _ in range(n)]
	cost[0] = a
	match = ''
	for i in range(1, n):
		match += s[i]
		while match:
			if match in s[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			cost[i] = min(cost[i - 1] + a, cost[i - len(match)] + b)
		else:
			cost[i] = cost[i - 1] + a
	print(cost[-1])
t = int(input())
for t_itr in range(t):
	(n, a, b) = map(int, input().split())
	s = input()
	solve()


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


import os
import sys

def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


p = int(input())
for r in range(p):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	t = 0
	t = [float('inf')] * (l + 1)
	t[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			t[j - 1] = min(t[i - 1] + b, t[j - 1])
			k = j
		t[i] = min(t[i - 1] + a, t[i])
		i += 1
	print(t[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


def solve():
	(N, A, B) = map(int, input().strip().split(' '))
	Cost = [0 for _ in range(N)]
	S = input().strip()
	Cost[0] = A
	match = ''
	for i in range(1, N):
		match += S[i]
		while match:
			if match in S[:i + 1 - len(match)]:
				break
			match = match[1:]
		if match:
			Cost[i] = min(Cost[i - 1] + A, Cost[i - len(match)] + B)
		else:
			Cost[i] = Cost[i - 1] + A
	print(Cost[-1])
T = int(input().strip())
for t in range(T):
	solve()


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = input()
	(dp, dp[0], res) = ([0] * n, a, '')
	for i in range(1, n):
		res += s[i]
		while res:
			if res in s[:i + 1 - len(res)]:
				break
			else:
				res = res[1:]
		if res:
			dp[i] = min(dp[i - 1] + a, dp[i - len(res)] + b)
		else:
			dp[i] = dp[i - 1] + a
	print(dp[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


samples_size = int(input())
for idx in range(samples_size):
	(N, A, B) = [int(ss) for ss in input().split()]
	_str = input()
	assert N == len(_str)
	_s = _str[::-1]
	cost = pos = 0
	s = ''

	def calc_cost(l):
		return B if l > 1 else A

	def find_part_size(start_pos):
		size = 0
		sle = ('', '')
		while True:
			size += 1
			s = (_s[start_pos:start_pos + size + 1], _s[start_pos + size + 1:])
			if s[1].find(s[0]) == -1:
				break
			sle = s
		return (size, sle)
	while pos < N:
		flag = False
		(size, sle) = find_part_size(pos)
		if size > 1:
			(nsize, nsle) = find_part_size(pos + size)
			(dsize, dsle) = find_part_size(pos + 1)
			nl = size + nsize
			dl = 1 + dsize
			dcost = calc_cost(1) + calc_cost(dsize)
			ncost = calc_cost(size) + calc_cost(nsize)
			while True:
				if nl >= dl and ncost <= dcost:
					flag = True
					break
				elif nl <= dl and ncost >= dcost:
					flag = False
					break
				elif nl <= dl and ncost < dcost:
					(nlen, _) = find_part_size(pos + nl)
					ncost += calc_cost(nlen)
					nl += nlen
				elif nl > dl and ncost > dcost:
					(dlen, _) = find_part_size(pos + dl)
					dcost += calc_cost(dlen)
					dl += dlen
				else:
					raise RuntimeError('unexpected')
		if flag:
			s += _s[pos:pos + size]
			pos += size
			cost += B
		else:
			s += _s[pos:pos + 1]
			pos += 1
			cost += A
	s = s[::-1]
	assert s == _str
	print(cost)


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


import math
import os
import random
import re
import sys
rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])


rep = int(input())
for r in range(rep):
	(l, a, b) = map(int, input().split(' '))
	s = input().strip()
	i = 1
	cost = 0
	cost = [float('inf')] * (l + 1)
	cost[0] = 0
	k = 0
	while i <= l:
		j = max(i, k)
		while j <= l and s[i - 1:j] in s[:i - 1]:
			j += 1
		if j - 1 != i:
			cost[j - 1] = min(cost[i - 1] + b, cost[j - 1])
			k = j
		cost[i] = min(cost[i - 1] + a, cost[i])
		i += 1
	print(cost[-1])