AtCoder Grand Contest 021 - Reversed LCS

Takahashi has decided to give a string to his mother.

The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T. That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).

Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value. Find the highest possible value achievable.

Constraints

* 1 \leq |S| \leq 300
* 0 \leq K \leq |S|
* S consists of lowercase English letters.
* K is an integer.

Input

Input is given from Standard Input in the following format:


S
K


Output

Print the highest possible value achievable.

Examples

Input

abcabcabc
1


Output

7


Input

atcodergrandcontest
3


Output

15

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
readline = sys.stdin.readline
S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())
if N == 1:
	ans = 1
elif N == 2:
	ans = 1
	if S[1] == S[2]:
		ans = 2
	if K:
		ans = 2
else:
	dp1 = [[0] * (K + 1) for _ in range(N + 2)]
	dp2 = [[0] * (K + 1) for _ in range(N + 2)]
	for i in range(1, N + 1):
		dp1[i][0] = 1
	for i in range(1, N):
		dp2[i][0] = 1
		if S[i] == S[i + 1]:
			dp2[i][0] = 2
		elif K:
			dp2[i][1] = 2
	for s in range(3, N + 1):
		dp3 = [[0] * (K + 1) for _ in range(N + 2)]
		for i in range(1, N - s + 2):
			j = i + s - 1
			if S[i] == S[j]:
				for k in range(K + 1):
					dp3[i][k] = max(dp2[i + 1][k], dp2[i][k], 2 + dp1[i + 1][k])
			else:
				dp3[i][0] = max(dp2[i + 1][0], dp2[i][0], dp2[i + 1][0])
				for k in range(1, K + 1):
					dp3[i][k] = max(dp2[i + 1][k], dp2[i][k], dp1[i + 1][k], 2 + dp1[i + 1][k - 1])
		dp1 = [k[:] for k in dp2]
		dp2 = [k[:] for k in dp3]
	ans = max((dp3[1][k] for k in range(K + 1)))
print(ans)


def main():
	s = input()
	n = len(s)
	k = int(input())
	dp = [[[1] * (n - i) for i in range(n)] for _ in range(k + 1)]
	if n == 1:
		print(1)
		return
	dp2 = dp[0][1]
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			dp2[i] = 2
	if k > 0:
		for cnt in range(1, k + 1):
			dp2 = dp[cnt][1]
			for i in range(n - 1):
				dp2[i] = 2
	for cnt in range(k):
		dp2 = dp[cnt]
		for d in range(2, n):
			dp3 = dp2[d]
			for left in range(n - d):
				right = left + d
				plus = (s[left] == s[right]) * 2
				dp3[left] = max(dp3[left], dp2[d - 1][left], dp2[d - 1][left + 1], dp2[d - 2][left + 1] + plus)
				dp[cnt + 1][d][left] = max(dp[cnt + 1][d][left], dp3[left], dp2[d - 2][left + 1] + 2)
	dp2 = dp[k]
	for d in range(2, n):
		dp3 = dp2[d]
		for left in range(n - d):
			right = left + d
			plus = (s[left] == s[right]) * 2
			dp3[left] = max(dp3[left], dp2[d - 1][left], dp2[d - 1][left + 1], dp2[d - 2][left + 1] + plus)
	print(dp[-1][-1][0])
main()


def solve(s, k):
	n = len(s)
	if k >= n // 2:
		return n
	dpp = [[1] * (k + 1), [0] * (k + 1)]
	for r in range(1, n):
		dpc = [[0] * (k + 1) for _ in range(r + 2)]
		dpc[r] = [1] * (k + 1)
		for l in range(r - 1, -1, -1):
			(dpl, dpl1) = (dpc[l], dpp[l + 1])
			if s[l] == s[r]:
				dpc[l] = [c + 2 for c in dpl1]
			else:
				(dppl, dpcl1) = (dpp[l], dpc[l + 1])
				dpl[0] = max(dppl[0], dpcl1[0])
				for p in range(1, k + 1):
					dpl[p] = max(dppl[p], dpcl1[p], dpl1[p - 1] + 2)
		dpp = dpc
	return dpp[0][k]
print(solve(input(), int(input())))


import sys
S = input()
S = ' ' + S
K = int(input())
N = len(S) - 1
if N == 1:
	print(1)
	sys.exit()
elif N == 2:
	if S[1] == S[2] or K > 0:
		print(2)
	else:
		print(1)
	sys.exit()
dp = [[[0] * (K + 1) for i in range(N + 2)]]
ans = 0
for i in range(1, N + 1):
	dp.append([[0] * (K + 1) for i in range(N + 2)])
	for j in range(N, i, -1):
		for k in range(K + 1):
			if S[i] == S[j]:
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j + 1][k] + 1)
			else:
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k], dp[i][j + 1][k])
				if k != 0:
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j + 1][k - 1] + 1)
			if i + 1 == j:
				ans = max(ans, dp[i][j][k] * 2)
			else:
				ans = max(ans, dp[i][j][k] * 2 + 1)
	dp[i - 1] = []
print(ans)


def solve(s, k):
	n = len(s)
	pdp = [[0] * (k + 1) for _ in range(n + 1)]
	for l in range(n - 1, -1, -1):
		dp = [[0] * (k + 1) for _ in range(n + 1)]
		for r in range(l, n):
			(dpr, dpr1) = (dp[r], pdp[r - 1])
			inc = 1 if l == r else 2
			is_same = s[l] == s[r]
			for p in range(k + 1):
				if is_same:
					dpr[p] = dpr1[p] + inc
				elif p:
					dpr[p] = max(pdp[r][p], dp[r - 1][p], dpr1[p - 1] + inc)
				else:
					dpr[p] = max(pdp[r][p], dp[r - 1][p])
		pdp = dp
	return pdp[-2][k]
print(solve(input(), int(input())))


import sys
input = sys.stdin.buffer.readline
S = list(input().rstrip())
K = int(input())
L = len(S)

def main():
	if K >= L // 2:
		ans = L
	else:
		dp = [[[0] * (K + 1) for _ in range(L + 1)] for _ in range(L + 1)]
		ans = 0
		for ind in reversed(range(L)):
			s = S[ind]
			for i in range(ind):
				for k in reversed(range(K + 1)):
					if S[i] == s:
						dp[i + 1][L - ind][k] = dp[i][L - ind - 1][k] + 1
					else:
						dp[i + 1][L - ind][k] = max(dp[i][L - ind][k], dp[i + 1][L - ind - 1][k])
						dp[i + 1][L - ind][k] = min(dp[i + 1][L - ind][k], min(i + 1, L - ind))
						if k < K and dp[i + 1][L - ind][k] == dp[i][L - ind - 1][k]:
							dp[i + 1][L - ind][k + 1] = max(dp[i + 1][L - ind][k + 1], dp[i + 1][L - ind][k] + 1)
							dp[i + 1][L - ind][k + 1] = min(dp[i + 1][L - ind][k + 1], min(i + 1, L - ind))
			for k in range(K + 1):
				ans = max(ans, 2 * dp[ind][L - ind][k])
				ans = max(ans, 2 * dp[ind][L - ind - 1][k] + 1)
			dp.pop()
	print(ans)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
s = input()
K = int(input())
n = len(s)
dp = [[[0] * (K + 1) for _ in range(n + 2 - i)] for i in range(n + 1)]
for i in range(n):
	for j in range(K + 1):
		dp[i][1][j] = 1
for l in range(2, n + 1):
	for i in range(n - l + 1):
		for k in range(K + 1):
			if s[i] == s[i + l - 1]:
				dp[i][l][k] = dp[i + 1][l - 2][k] + 2
			else:
				dp[i][l][k] = max(dp[i + 1][l - 1][k], dp[i][l - 1][k])
				if k >= 1:
					dp[i][l][k] = max(dp[i][l][k], dp[i + 1][l - 2][k - 1] + 2)
ans = max((dp[0][i][j] for i in range(n + 2) for j in range(K + 1)))
print(ans)


s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2 * K + 1 >= n:
	print(n)
	exit()
dp = [[[0 for i in range(K + 1)] for j in range(n + 1)] for k in range(n + 1)]
if n == 2 and K == 0:
	if s == t:
		print(2)
		exit()
	else:
		print(1)
		exit()
ans = min(2 * K + 1, n)
for center in range(1, n - 1):
	flg = 0
	sf = s[:center]
	sl = t[:n - center - 1]
	if s[center] == s[center + 1]:
		flg = 1
	sfl = len(sf)
	sll = len(sl)
	for j in range(1, sll + 1):
		dp[sfl][j][0] = max(dp[sfl - 1][j][0], dp[sfl][j - 1][0])
		if sf[-1] != sl[j - 1]:
			for k in range(1, K + 1):
				dp[sfl][j][k] = max(dp[sfl - 1][j - 1][k - 1] + 1, dp[sfl - 1][j][k], dp[sfl][j - 1][k])
		if sf[-1] == sl[j - 1]:
			dp[sfl][j][0] = max(dp[sfl][j][0], dp[sfl - 1][j - 1][0] + 1)
			for k in range(1, K + 1):
				dp[sfl][j][k] = max(dp[sfl - 1][j - 1][k - 1] + 1, dp[sfl - 1][j - 1][k] + 1, dp[sfl - 1][j][k], dp[sfl][j - 1][k])
	if flg:
		ans = max(dp[sfl][sll][K] * 2 + 1, dp[sfl][sll - 1][K] * 2 + 2, ans)
	elif K > 0:
		ans = max(dp[sfl][sll][K] * 2 + 1, dp[sfl][sll - 1][K - 1] * 2 + 2, ans)
	else:
		ans = max(dp[sfl][sll][K] * 2 + 1, ans)
print(ans)


def get_ind(l, r):
	mod = 3
	return OFFSET * (l % mod) + r
s = input()
n = len(s)
k = int(input())
dp = [[0] * ((n + 1) * 3) for i in range(k + 1)]
OFFSET = n + 1
for i in range(n):
	dp[0][get_ind(i, i + 1)] = 1
for length in range(2, n + 1):
	for l in range(n + 1):
		for ki in range(k + 1):
			r = l + length
			if r > n:
				break
			if s[l] == s[r - 1]:
				dp[ki][get_ind(l, r)] = max(2 + dp[ki][get_ind(l + 1, r - 1)], dp[ki][get_ind(l, r)])
			else:
				dp[ki][get_ind(l, r)] = max(dp[ki][get_ind(l + 1, r)], dp[ki][get_ind(l, r - 1)], dp[ki][get_ind(l, r)])
				if ki - 1 >= 0:
					dp[ki][get_ind(l, r)] = max(dp[ki - 1][get_ind(l + 1, r - 1)] + 2, dp[ki][get_ind(l, r)])
ans = 0
for i in range(k + 1):
	for j in range(3 * (n + 1)):
		ans = max(ans, dp[i][j])
print(ans)


import sys
readline = sys.stdin.buffer.readline
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))

def solve():
	s = list(ns())
	ls = len(s)
	lk = ni()
	dp = [[[0] * ls for _ in range(ls)] for i in range(2)]
	ans = 0
	for i in range(ls):
		dp[0][i][i] = 1
	for k in range(lk + 1):
		v = k & 1
		for dis in range(1, ls):
			for i in range(ls - dis):
				j = i + dis
				dp[v][i][j] = 0
				if s[i] == s[j]:
					dp[v][i][j] = dp[v][i + 1][j - 1] + 2
				elif k:
					dp[v][i][j] = dp[v ^ 1][i + 1][j - 1] + 2
				dp[v][i][j] = max(dp[v][i][j], dp[v][i + 1][j], dp[v][i][j - 1])
		ans = max(ans, dp[v][0][-1])
	print(ans)
	return
solve()


def examA():
	N = I()
	ans = 0
	print(ans)
	return

def examB():

	def norm2(vec):
		return math.sqrt(vec[0] ** 2 + vec[1] ** 2)

	def ConvexHull(point_list):
		pos2idx = {point_list[i]: i for i in range(len(point_list))}
		y_val = defaultdict(list)
		x_list = sorted(list(set([p[0] for p in point_list])))
		for (x, y) in point_list:
			y_val[x].append(y)
		upper = [(x_list[0], max(y_val[x_list[0]]))]
		lower = [(x_list[0], min(y_val[x_list[0]]))]
		prev = float('inf')
		for xi in x_list[1:]:
			(x0, y0) = upper[-1]
			(x1, y1) = (xi, max(y_val[xi]))
			if (y1 - y0) / (x1 - x0) < prev:
				upper.append((x1, y1))
				prev = (y1 - y0) / (x1 - x0)
			else:
				while True:
					(x0, y0) = upper[-1]
					if len(upper) == 1:
						upper.append((x1, y1))
						break
					(x00, y00) = upper[-2]
					if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
						upper.pop()
					else:
						prev = (y1 - y0) / (x1 - x0)
						upper.append((x1, y1))
						break
		prev = -float('inf')
		for xi in x_list[1:]:
			(x0, y0) = lower[-1]
			(x1, y1) = (xi, min(y_val[xi]))
			if (y1 - y0) / (x1 - x0) > prev:
				lower.append((x1, y1))
				prev = (y1 - y0) / (x1 - x0)
			else:
				while True:
					(x0, y0) = lower[-1]
					if len(lower) == 1:
						lower.append((x1, y1))
						break
					(x00, y00) = lower[-2]
					if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
						lower.pop()
					else:
						prev = (y1 - y0) / (x1 - x0)
						lower.append((x1, y1))
						break
		(upper_idx, lower_idx) = ([pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower])
		if upper_idx[-1] == lower_idx[-1]:
			upper_idx.pop()
		CH_idx = upper_idx
		CH_idx.extend(reversed(lower_idx))
		if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
			CH_idx.pop()
		return CH_idx
	N = I()
	P = [[] for _ in range(N)]
	D = defaultdict(int)
	for i in range(N):
		(x, y) = LI()
		P[i] = (x, y)
		D[x, y] = i
	C = ConvexHull(P)
	ans = [0] * N
	if len(C) == 2:
		for c in C:
			ans[c] = 0.5
		for v in ans:
			print(v)
		return
	for (i, c) in enumerate(C):
		(s, t, u) = (C[i - 1], C[i], C[(i + 1) % len(C)])
		(x0, y0) = P[s]
		(x1, y1) = P[t]
		(x2, y2) = P[u]
		vec0 = (y0 - y1, x1 - x0)
		vec1 = (y1 - y2, x2 - x1)
		ans[t] = math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)
	for v in ans:
		print(v)
	return

def examC():
	ans = 0
	print(ans)
	return

def examD():
	S = SI()
	N = len(S)
	K = I()
	if K > 150:
		K = 150
	dp = [[[0] * (K + 1) for _ in range(N)] for i in range(N)]
	for i in range(N):
		for j in range(K + 1):
			dp[i][i][j] = 1
	for i in range(2, N + 1):
		for k in range(K + 1):
			for (l, r) in enumerate(range(i - 1, N)):
				if S[l] == S[r]:
					dp[l][r][k] = dp[l + 1][r - 1][k] + 2
				elif k > 0:
					dp[l][r][k] = max(dp[l + 1][r][k], dp[l][r - 1][k], dp[l + 1][r - 1][k - 1] + 2)
				else:
					dp[l][r][k] = max(dp[l + 1][r][k], dp[l][r - 1][k])
	ans = max(dp[0][-1])
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
from decimal import Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 7)
examD()


S = input()
K = int(input())
N = len(S)
if K * 2 >= N - 1:
	print(N)
	exit()
dp = [[[0 for _ in range(K + 1)] for _ in range(N)] for _ in range(N)]
for i in range(N):
	for k in range(K + 1):
		dp[i][i][k] = 1
for _j in range(1, N):
	for i in range(N):
		j = i + _j
		if j < N:
			for k in range(K + 1):
				dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k], dp[i][j - 1][k])
				if _j == 1:
					if S[i] == S[j]:
						dp[i][j][k] = 2
					elif k + 1 <= K:
						dp[i][j][k + 1] = 2
				elif S[i] == S[j]:
					dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j - 1][k] + 2)
				elif k + 1 <= K:
					dp[i][j][k + 1] = max(dp[i][j][k], dp[i + 1][j - 1][k] + 2)
print(max(dp[0][N - 1]))