Problem Description

Little F and Little Y often play together. Since Little F is a painter, he likes to draw on a grid of length $n$ and width $1$. The $i$-th cell from left to right is painted with a color $a_i$.

You think his random doodles look too ugly, so you want to keep exactly $k$ colors (you are not allowed to keep colors that do not appear in the grid). All cells that are not painted with any color you keep will be cut off, and some cells will remain in the end. You want the color indices of the remaining cells, from left to right, to be monotonically non-decreasing.

In addition, the $i$-th color used by Little Y has a value $b_i$. Little Y is very happy after seeing the grid you cropped, so he decides to pay you the sum of the values of the colors you chose.

You need to find the maximum total value you can obtain.

Input Format

The first line contains two integers $n,k$, representing the size of the grid Little Y drew and the number of colors you need to keep.
The second line contains $n$ integers $a_i$, representing the color of the $i$-th cell from left to right in the grid drawn by Little Y.
The third line contains $n$ integers $b_i$, representing the value of the $i$-th color.

Output Format

Output one integer, representing the maximum value you can obtain. In particular, if it is impossible to find a way to choose colors that satisfies the requirements, output $-1$.

5 2
1 2 1 3 2
5 3 1 100 100

6

10 3
1 3 4 2 9 3 4 2 5 1
1 5 2 3 9 8 1 2 3 10

-1

Hint

Sample Explanation #1

For the first sample, we can choose to keep colors $1$ and $3$. The remaining grid is $[1,1,3]$, which satisfies the monotonically non-decreasing constraint. The value obtained is $b_1+b_3=5+1=6$, and it can be proven that this is optimal.

Constraints

For all testdata, $1 \le n \le 500$, $1 \le k \le 500$, $1 \le a_i \le n$, $1 \le b_i \le 10^9$.

This problem uses bundled tests. All test points with the same constraints are bundled into one $\text{Subtask}$.

The additional constraints of each test point are shown in the table below.

Translated by ChatGPT 5