Indian National Olympiad in Informatics 2016
	There are k types of brackets each with its own opening bracket and closing bracket. We assume that the first pair is denoted by the numbers 1 and k+1, the second by 2 and k+2 and so on. Thus the opening brackets are denoted by 1,2,.., k, and the corresponding closing brackets are denoted by k+1,k+2,..., 2*k respectively.

	Some sequences with elements from 1,2, ... 2*k form well-bracketed sequences while others don't. A sequence is well-bracketed, if we can match or pair up opening brackets and closing brackets of the same type in such a way that the following holds:

	 1) every bracket is paired up

	 2) in each matched pair, the opening bracket occurs before the closing bracket

	 3) for a matched pair, any other matched pair lies either completely between them or outside them.

	For the examples discussed below, let us assume that k = 2. The sequence 1,1,3 is not well-bracketed as one of the two 1's cannot be paired. The sequence 3,1,3,1 is not well-bracketed as there is no way to match the second 1 to a closing bracket occurring after it. The sequence 1,2,3,4 is not well-bracketed as the matched pair 2,4 is neither completely between the matched pair 1,3 nor completely outside it. That is, the matched pairs cannot overlap. The sequence 1,2,4,3,1,3 is well-bracketed. We match the first 1 with the first 3, the 2 with the 4 and the second 1 with the second 3, satisfying all the 3 conditions. If you rewrite these sequences using [,{,],} instead of 1,2,3,4 respectively, this will be quite clear.

	In this problem you are given a sequence of brackets, of length N: B[1], .., B[N], where each B[i] is one of the brackets. You are also given an array of Values: V[1],.., V[N].

	Among all the subsequences in the Values array, such that the corresponding bracket subsequence in the B Array is a well-bracketed sequence, you need to find the maximum sum. Suppose N = 6, k = 3 and the values of V and B are as follows:

i	1	2	3	4	5	6
V[i]	4	5	-2	1	1	6
B[i]	1	3	4	2	5	6

	Then, the brackets in positions 1,3 form a well-bracketed sequence (1,4) and the sum of the values in these positions is 2 (4 + -2 = 2). The brackets in positions 1,3,4,5 form a well-bracketed sequence (1,4,2,5) and the sum of the values in these positions is 4. Finally, the brackets in positions 2,4,5,6 forms a well-bracketed sequence (3,2,5,6) and the sum of the values in these positions is 13. The sum of the values in positions 1,2,5,6 is 16 but the brackets in these positions (1,3,5,6) do not form a well-bracketed sequence. You can check the best sum from positions whose brackets form a well-bracketed sequence is 13.


-----Input format-----
	One line, which contains (2*N + 2) space separate integers. The first integer denotes N. The next integer is k. The next N integers are V[1],..., V[N]. The last N integers are B[1],.., B[N].


-----Output format-----
	One integer, which is the maximum sum possible satisfying the requirement mentioned above. 


-----Test data-----

		1 ≤ k ≤ 7

		-106 ≤ V[i] ≤ 106, for all i

		1 ≤ B[i] ≤ 2*k, for all i.
	
Subtask 1 (40 Marks) 1 ≤ n ≤ 10.
Subtask 2 (60 Marks) 1 ≤ n ≤ 700.


-----Sample Input-----
6 3 4 5 -2 1 1 6 1 3 4 2 5 6

-----Sample Output-----
13

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import bisect
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        if b_l[j+k] >= k1:
            left = bisect.bisect_right(b_inv[b_l[j+k]-k1], j)
            
            if b_l[j+k] >= k1:
                for i in b_inv[b_l[j+k]-k1][left:]:
                    if i > j+k:
                        break
                    if i > j:
                        dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
                
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        

print(dp[0][-1])

a,b,*c=list(map(int,input().strip().split()))
d=[]
e=[]
for i in range(a):
    e.append(c[i])
    d.append(c[i+a])
DP1=[[-1 for i in range(a)] for j in range(a)]
def DP(l,r):
    nonlocal d,e,b,DP1
    if l>=r:
        return 0
    elif DP1[l][r]!=-1:
        return DP1[l][r]
    else:
        DP1[l][r]=max(DP1[l][r],DP(l+1,r))
        DP1[l][r]=max(DP1[l][r],DP(l,r-1))
        if d[l]+b==d[r]:
            DP1[l][r]=max(DP1[l][r],e[l]+e[r]+DP(l+1,r-1))
        for i in range(l,r):
            if d[l]+b==d[i] or d[i]+b==d[r]:
                DP1[l][r]=max(DP1[l][r],DP(l,i)+DP(i+1,r))
    return DP1[l][r]
print(DP(0,a-1))


a,b,*c=list(map(int,input().strip().split()))
d=[]
e=[]
for i in range(a):
    e.append(c[i])
    d.append(c[i+a])
DP1=[[-1 for i in range(a)] for j in range(a)]
def DP(l,r):
    nonlocal d,e,b,DP1
    if l>=r:
        return 0
    elif DP1[l][r]!=-1:
        return DP1[l][r]
    else:
        #DP1[l][r]=max(DP1[l][r],DP(l+1,r))
        #DP1[l][r]=max(DP1[l][r],DP(l,r-1))
        if d[l]+b==d[r]:
            DP1[l][r]=max(DP1[l][r],e[l]+e[r]+DP(l+1,r-1))
        for i in range(l,r):
            DP1[l][r]=max(DP1[l][r],DP(l,i)+DP(i+1,r))
    return DP1[l][r]
print(DP(0,a-1))


# cook your dish here
import bisect
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        if b_l[j+k] >= k1:
            left = bisect.bisect_right(b_inv[b_l[j+k]-k1], j)
            
            if b_l[j+k] >= k1:
                for i in b_inv[b_l[j+k]-k1][left:]:
                    if i > j+k:
                        break
                    if i > j:
                        dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
                
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        

print(dp[0][-1])

# cook your dish here
inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
brac={i:set() for i in range(n)}
for i in range(n):
    for j in range(i+1,n):
        if b[j]-b[i]==k:
            brac[i].add(j)
        
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if i+j in brac[i]:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in brac[i]:
            if l>=i+j:
                continue
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])


# cook your dish here
import bisect
# def recur(s_i, e_i, end_i):
#     # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
#     #     return dp[s_i][end_i][e_i]
        
#     inside = 0
#     for i in range(s_i+1, e_i):
#         if b_l[i] < k:
#             if e_i not in dp[i]:
#                 dp[i][e_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < e_i:
#                         dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
#             inside = max(inside, dp[i][e_i])
#     outside = 0
#     for i in range(e_i+1, min(n, end_i)):
#         if b_l[i] < k:
#             if end_i not in dp[i]:
#                 dp[i][end_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < end_i:
#                         dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
#             outside = max(outside, dp[i][end_i])
                    
#     # if end_i not in dp[s_i]:
#     #     dp[s_i][end_i] = {}
#     # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
#     # return dp[s_i][end_i][e_i]
#     return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        if b_l[j+k] >= k1:
            left = bisect.bisect_right(b_inv[b_l[j+k]-k1], j)
            
            if b_l[j+k] >= k1:
                for i in b_inv[b_l[j+k]-k1][left:]:
                    if i > j+k:
                        break
                    if i > j:
                        dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
                
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        
# dp = [{} for _ in range(n)]
# ans = 0
# for i in range(n):
#     if b_l[i] < k:
#         if n+1 not in dp[i]:
#             dp[i][n+1] = 0
#             bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#             for ind in b_inv[b_l[i]+k][bi_i:]:
#                 if i < ind:
#                     dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
#         ans = max(ans, dp[i][n+1])
# print(dp)
print(dp[0][-1])

# cook your dish here
import bisect
# def recur(s_i, e_i, end_i):
#     # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
#     #     return dp[s_i][end_i][e_i]
        
#     inside = 0
#     for i in range(s_i+1, e_i):
#         if b_l[i] < k:
#             if e_i not in dp[i]:
#                 dp[i][e_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < e_i:
#                         dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
#             inside = max(inside, dp[i][e_i])
#     outside = 0
#     for i in range(e_i+1, min(n, end_i)):
#         if b_l[i] < k:
#             if end_i not in dp[i]:
#                 dp[i][end_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < end_i:
#                         dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
#             outside = max(outside, dp[i][end_i])
                    
#     # if end_i not in dp[s_i]:
#     #     dp[s_i][end_i] = {}
#     # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
#     # return dp[s_i][end_i][e_i]
#     return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        if b_l[j+k] >= k1:
            left = bisect.bisect_left(b_inv[b_l[j+k]-k1], j)
            
            if b_l[j+k] >= k1:
                for i in b_inv[b_l[j+k]-k1][left:]:
                    if i > j+k:
                        break
                    dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
                
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        
# dp = [{} for _ in range(n)]
# ans = 0
# for i in range(n):
#     if b_l[i] < k:
#         if n+1 not in dp[i]:
#             dp[i][n+1] = 0
#             bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#             for ind in b_inv[b_l[i]+k][bi_i:]:
#                 if i < ind:
#                     dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
#         ans = max(ans, dp[i][n+1])
# print(dp)
print(dp[0][-1])

# cook your dish here
# import bisect
# def recur(s_i, e_i, end_i):
#     # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
#     #     return dp[s_i][end_i][e_i]
        
#     inside = 0
#     for i in range(s_i+1, e_i):
#         if b_l[i] < k:
#             if e_i not in dp[i]:
#                 dp[i][e_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < e_i:
#                         dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
#             inside = max(inside, dp[i][e_i])
#     outside = 0
#     for i in range(e_i+1, min(n, end_i)):
#         if b_l[i] < k:
#             if end_i not in dp[i]:
#                 dp[i][end_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < end_i:
#                         dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
#             outside = max(outside, dp[i][end_i])
                    
#     # if end_i not in dp[s_i]:
#     #     dp[s_i][end_i] = {}
#     # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
#     # return dp[s_i][end_i][e_i]
#     return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        if b_l[j+k] >= k1:
            for i in reversed(b_inv[b_l[j+k]-k1]):
                if i <= j:
                    break
                dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
            
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        
# dp = [{} for _ in range(n)]
# ans = 0
# for i in range(n):
#     if b_l[i] < k:
#         if n+1 not in dp[i]:
#             dp[i][n+1] = 0
#             bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#             for ind in b_inv[b_l[i]+k][bi_i:]:
#                 if i < ind:
#                     dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
#         ans = max(ans, dp[i][n+1])
# print(dp)
print(dp[0][-1])

# cook your dish here
# import bisect
# def recur(s_i, e_i, end_i):
#     # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
#     #     return dp[s_i][end_i][e_i]
        
#     inside = 0
#     for i in range(s_i+1, e_i):
#         if b_l[i] < k:
#             if e_i not in dp[i]:
#                 dp[i][e_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < e_i:
#                         dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
#             inside = max(inside, dp[i][e_i])
#     outside = 0
#     for i in range(e_i+1, min(n, end_i)):
#         if b_l[i] < k:
#             if end_i not in dp[i]:
#                 dp[i][end_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < end_i:
#                         dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
#             outside = max(outside, dp[i][end_i])
                    
#     # if end_i not in dp[s_i]:
#     #     dp[s_i][end_i] = {}
#     # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
#     # return dp[s_i][end_i][e_i]
#     return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k1)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        
        dp[j][j+k] = max(dp[j][j+k], dp[j][j+k-1])
        dp[j][j+k] = max(dp[j][j+k], dp[j+1][j+k])
        if b_l[j+k] >= k1:
            for i in b_inv[b_l[j+k]-k1]:
                dp[j][j+k] = max(dp[j][j+k], dp[j][i-1]+dp[i][j+k])
            
        if b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        
# dp = [{} for _ in range(n)]
# ans = 0
# for i in range(n):
#     if b_l[i] < k:
#         if n+1 not in dp[i]:
#             dp[i][n+1] = 0
#             bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#             for ind in b_inv[b_l[i]+k][bi_i:]:
#                 if i < ind:
#                     dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
#         ans = max(ans, dp[i][n+1])
# print(dp)
print(dp[0][-1])

# cook your dish here
# import bisect
# def recur(s_i, e_i, end_i):
#     # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
#     #     return dp[s_i][end_i][e_i]
        
#     inside = 0
#     for i in range(s_i+1, e_i):
#         if b_l[i] < k:
#             if e_i not in dp[i]:
#                 dp[i][e_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < e_i:
#                         dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
#             inside = max(inside, dp[i][e_i])
#     outside = 0
#     for i in range(e_i+1, min(n, end_i)):
#         if b_l[i] < k:
#             if end_i not in dp[i]:
#                 dp[i][end_i] = 0
#                 bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#                 for ind in b_inv[b_l[i]+k][bi_i:]:
#                     if i < ind < end_i:
#                         dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
#             outside = max(outside, dp[i][end_i])
                    
#     # if end_i not in dp[s_i]:
#     #     dp[s_i][end_i] = {}
#     # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
#     # return dp[s_i][end_i][e_i]
#     return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k1, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

# b_inv = {key:[] for key in range(2*k)}
for i in range(n):
    b_l[i] -= 1
    # b_inv[b_l[i]].append(i)

dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1, n):
    for j in range(n-2, -1, -1):
        if j+k >= n:
            continue
        elif b_l[j+k]-k1 == b_l[j]:
            if j+k-1 < n:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j]+dp[j+1][j+k-1])
            else:
                dp[j][j+k] = max(dp[j][j+k], v_l[j+k]+v_l[j])
        for i in range(j, j+k):
            dp[j][j+k] = max(dp[j][j+k], dp[j][i]+dp[i+1][j+k])
        
# dp = [{} for _ in range(n)]
# ans = 0
# for i in range(n):
#     if b_l[i] < k:
#         if n+1 not in dp[i]:
#             dp[i][n+1] = 0
#             bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
#             for ind in b_inv[b_l[i]+k][bi_i:]:
#                 if i < ind:
#                     dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
#         ans = max(ans, dp[i][n+1])
# print(dp)
print(dp[0][-1])

# cook your dish here
import bisect
def recur(s_i, e_i, end_i):
    # if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
    #     return dp[s_i][end_i][e_i]
        
    inside = 0
    for i in range(s_i+1, e_i):
        if b_l[i] < k:
            if e_i not in dp[i]:
                dp[i][e_i] = 0
                bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
                for ind in b_inv[b_l[i]+k][bi_i:]:
                    if i < ind < e_i:
                        dp[i][e_i] = max(dp[i][e_i], recur(i, ind, e_i))
            inside = max(inside, dp[i][e_i])
    outside = 0
    for i in range(e_i+1, min(n, end_i)):
        if b_l[i] < k:
            if end_i not in dp[i]:
                dp[i][end_i] = 0
                bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
                for ind in b_inv[b_l[i]+k][bi_i:]:
                    if i < ind < end_i:
                        dp[i][end_i] = max(dp[i][end_i], recur(i, ind, end_i))
            outside = max(outside, dp[i][end_i])
                    
    # if end_i not in dp[s_i]:
    #     dp[s_i][end_i] = {}
    # dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
    # return dp[s_i][end_i][e_i]
    return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [{} for _ in range(n)]
ans = 0
for i in range(n):
    if b_l[i] < k:
        if n+1 not in dp[i]:
            dp[i][n+1] = 0
            bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
            for ind in b_inv[b_l[i]+k][bi_i:]:
                if i < ind:
                    dp[i][n+1] = max(dp[i][n+1], recur(i, ind, n+1))
        ans = max(ans, dp[i][n+1])
# print(dp)
print(ans)

# cook your dish here
import bisect
def recur(s_i, e_i, end_i):
    if end_i in dp[s_i] and e_i in dp[s_i][end_i]:
        return dp[s_i][end_i][e_i]
        
    inside = 0
    for i in range(s_i+1, e_i):
        if b_l[i] < k:
            bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
            for ind in b_inv[b_l[i]+k][bi_i:]:
                if i < ind < e_i:
                    inside = max(inside, recur(i, ind, e_i))
    outside = 0
    for i in range(e_i+1, min(n, end_i)):
        if b_l[i] < k:
            bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
            for ind in b_inv[b_l[i]+k][bi_i:]:
                if i < ind < end_i:
                    outside = max(outside, recur(i, ind, end_i))
    if end_i not in dp[s_i]:
        dp[s_i][end_i] = {}
    dp[s_i][end_i].update({e_i: v_l[s_i] + v_l[e_i] + outside + inside})
    return dp[s_i][end_i][e_i]
    
n, k, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [{} for _ in range(n)]
ans = 0
for i in range(n):
    if b_l[i] < k:
        bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
        for ind in b_inv[b_l[i]+k][bi_i:]:
            if i < ind:
                ans = max(ans, recur(i, ind, n+1))
# print(dp)
print(ans)

# cook your dish here
import bisect
def recur(s_i, e_i, end_i):
    inside = 0
    for i in range(s_i+1, e_i):
        if b_l[i] < k:
            bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
            for ind in b_inv[b_l[i]+k][bi_i:]:
                if i < ind < e_i:
                    dp[i][e_i] = recur(i, ind, e_i)
                    inside = max(inside, dp[i][e_i])
    outside = 0
    for i in range(e_i+1, min(n, end_i)):
        if b_l[i] < k:
            bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
            for ind in b_inv[b_l[i]+k][bi_i:]:
                if i < ind < end_i:
                    dp[i][end_i] = recur(i, ind, end_i)
                    outside = max(outside, dp[i][end_i])
    return v_l[s_i] + v_l[e_i] + outside + inside
    
n, k, *l = map(int, input().split())
v_l, b_l = l[:n], l[n:]

b_inv = {key:[] for key in range(2*k)}
for i in range(n):
    b_l[i] -= 1
    b_inv[b_l[i]].append(i)

dp = [{} for _ in range(n)]
ans = 0
for i in range(n):
    if b_l[i] < k:
        bi_i = bisect.bisect_left(b_inv[b_l[i]+k], i)
        for ind in b_inv[b_l[i]+k][bi_i:]:
            if i < ind:
                dp[i][n+1] = recur(i, ind, n+1)
                ans = max(ans, dp[i][n+1])
# print(dp)
print(ans)

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 21:18

"""

L = [int(x) for x in input().split()]
N = L[0]
K = L[1]
V = L[2: 2+N]
B = L[2+N:]

# N = 700
# K = 7
# V = [random.randint(0, 10) for _ in range(N)]
# B = [random.randint(1, K*2) for _ in range(N)]
# N, K = 6, 3
# V = [4, 5, -2, 1, 1, 6]
# B = [1, 3, 4, 2, 5, 6]

# t0 = time.time()
bi = collections.defaultdict(list)
for i, v in enumerate(B):
    bi[v].append(i)


dp = [[float('-inf') for _ in range(N+1)] for _ in range(N)]
for i in range(N):
    dp[i][1] = 0
    dp[i][0] = 0

ans = 0
for l in range(2, N+1):
    for s in range(N-l+1):
        t = s+l-1
        dp[s][l] = max(dp[s][l], dp[s][l-1])

        pres = bi[B[t]-K]
        pl, pr = bisect.bisect_left(pres, s), bisect.bisect_right(pres, t)
        for i in pres[pl: pr]:
            dp[s][l] = max(dp[s][l], V[i] + V[t] + dp[s][max(i-s, 0)] + dp[i+1][max(t-i-1, 0)])
            ans = max(ans, dp[s][l])
print(ans)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 21:18

"""

L = [int(x) for x in input().split()]
N = L[0]
K = L[1]
V = L[2: 2+N]
B = L[2+N:]

# N = 700
# K = 7
# V = [random.randint(0, 10) for _ in range(N)]
# B = [random.randint(1, K*2) for _ in range(N)]
# N, K = 6, 3
# V = [4, 5, -2, 1, 1, 6]
# B = [1, 3, 4, 2, 5, 6]

# t0 = time.time()
bi = [[] for _ in range(20)]
L = []
for i, v in enumerate(B):
    bi[v].append(i)
    if v <= K:
        L.append(i)


dp = [[float('-inf') for _ in range(N+1)] for _ in range(N)]
for i in range(N):
    dp[i][1] = 0
    dp[i][0] = 0

ans = 0
for l in range(2, N+1):
    for s in range(N-l+1):
        t = s+l-1
        dp[s][l] = max(dp[s][l], dp[s][l-1])

        pres = bi[B[t]-K]
        pl, pr = bisect.bisect_left(pres, s), bisect.bisect_right(pres, t)
        for i in pres[pl: pr]:
            dp[s][l] = max(dp[s][l], V[i] + V[t] + dp[s][max(i-s, 0)] + dp[i+1][max(t-i-1, 0)])
            ans = max(ans, dp[s][l])
print(ans)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 21:18

"""

L = [int(x) for x in input().split()]
N = L[0]
K = L[1]
V = L[2: 2+N]
B = L[2+N:]

# N = 700
# K = 7
# V = [random.randint(0, 10) for _ in range(N)]
# B = [random.randint(1, K*2) for _ in range(N)]
# N, K = 6, 3
# V = [4, 5, -2, 1, 1, 6]
# B = [1, 3, 4, 2, 5, 6]

# t0 = time.time()
bi = [[] for _ in range(20)]
L = []
for i, v in enumerate(B):
    bi[v].append(i)
    if v <= K:
        L.append(i)


dp = [[float('-inf') for _ in range(N+1)] for _ in range(N)]
for i in range(N):
    dp[i][1] = 0
    dp[i][0] = 0

ans = 0
for l in range(2, N+1):
    for s in range(N-l+1):
        t = s+l-1
        dp[s][l] = max(dp[s][l], dp[s][l-1])
        for i in range(s, t+1):
            if B[i] + K == B[t]:
                dp[s][l] = max(dp[s][l], V[i] + V[t] + dp[s][max(i-s, 0)] + dp[i+1][max(t-i-1, 0)])
                ans = max(ans, dp[s][l])
print(ans)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 21:18

"""

L = [int(x) for x in input().split()]

N = L[0]
K = L[1]
V = L[2: 2+N]
B = L[2+N:]


bi = collections.defaultdict(list)
for i, v in enumerate(B):
    bi[v].append(i)


memo = {}


def dfs(l, r):
    if l >= r:
        return 0

    k = (l, r)
    if k in memo:
        return memo[k]

    ans = 0
    for i in range(l, r):
        br = bi[B[i]+K]
        jl, jr = bisect.bisect_left(br, i), bisect.bisect_right(br, r)
        for j in br[jl: jr]:
            if i < j <= r:
                ans = max(ans, V[i]+V[j] + dfs(i+1, j-1) + dfs(j+1, r))
    memo[k] = ans

    return ans


print(dfs(0, N-1))

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 21:18

"""

L = [int(x) for x in input().split()]

N = L[0]
K = L[1]
V = L[2: 2+N]
B = L[2+N:]


bi = collections.defaultdict(list)
for i, v in enumerate(B):
    bi[v].append(i)


memo = {}


def dfs(l, r):
    if l >= r:
        return 0

    k = (l, r)
    if k in memo:
        return memo[k]

    ans = 0
    for i in range(l, r):
        for j in bi[B[i]+K]:
            if i < j <= r:
                ans = max(ans, V[i]+V[j] + dfs(i+1, j-1) + dfs(j+1, r))
    memo[k] = ans

    return ans


print(dfs(0, N-1))

# cook your dish here
inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
brac={i:set() for i in range(n)}
for i in range(n):
    for j in range(i+1,n):
        if b[j]-b[i]==k:
            brac[i].add(j)
        
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if i+j in brac[i]:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in brac[i]:
            if l>=i+j:
                continue
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])


# cook your dish here
inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if b[i+j]-b[i]==k:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in range(i+1,i+j):
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])



# cook your dish here
inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if b[i+j]-b[i]==k:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in range(i+1,i+j):
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])


inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
brac={i:set() for i in range(n)}
for i in range(n):
    for j in range(i+1,n):
        if b[j]-b[i]==k:
            brac[i].add(j)
        
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if i+j in brac[i]:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in brac[i]:
            if l>=i+j:
                continue
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])


inpu=list(map(int,input().split()))
n,k=inpu[0],inpu[1]
v=inpu[2:n+2]
b=inpu[n+2:2*n+2]
dp=[[0 for i in range(n)] for j in range(n)]
for j in range(1,n):
    for  i in range(n-j):
        ans=-float("inf")
        if b[i+j]-b[i]==k:
            if j==1:
                ans=max(ans,v[i+j]+v[i])
            else:
                ans=max(ans,v[i+j]+v[i]+dp[i+1][i+j-1])
        for l in range(i+1,i+j):
            if b[l]-b[i]==k:
                if l==i+1:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j])
                else:
                    ans=max(ans,v[l]+v[i]+dp[l+1][i+j]+dp[i+1][l-1])
        ans=max(ans,dp[i+1][i+j])
        dp[i][i+j]=ans
print(dp[0][n-1])