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, \ldots , k\), and the corresponding closing brackets are denoted by \(k+1, k+2, \ldots, 2k\) respectively.
Some sequences with elements from \(1, 2, \ldots, 2k\) form well bracketed sequences while others don't. A sequence is well bracketed, if we can match or pair up opening brackets of the same type in such a way that the following holds:
In this problem you are given a sequence of brackets, of length \(N\): \(B, \ldots , B[N]\), where each \(B[i]\) is one of the brackets. You are also given an array of Values: \(V,\ldots, 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.
Task: Solve the above problem for this input.
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,..., V[N]. The last N integers are B,.., B[N].
*Suppose N = 6, k = 3 and the values of V and B are as follows:
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.