Maximize Color Value with Non‐decreasing Segments

A painter, Xiao F, has painted a 1-dimensional grid with n cells. The i-th cell (from the left) is filled with a color denoted by \(a_i\). You decide that his random scribbles are too messy, so you want to keep exactly \(k\) colors (you cannot choose a color that does not appear on the grid). To do so, you remove (cut off) all cells that are not painted in any of your chosen colors. After that, the remaining cells form a sequence. You wish that the color numbers in this sequence, read from left to right, are in non-decreasing order.

In addition, Xiao Y assigns a value to each color. The \(i\)-th color has a value \(b_i\). Impressed by your neat grid after cutting, Xiao Y offers you a payment equal to the sum of the values of the colors you have kept.

Your task is to choose exactly \(k\) colors (which must be colors that appear in the grid) so that when you remove all cells not painted in these colors, the remaining sequence is sorted in non-decreasing order. Under this constraint, compute the maximum total value you can obtain. If it is impossible to choose \(k\) colors satisfying the condition, output -1.

Note on the ordering condition: Suppose for a chosen color the first occurrence is \(f\) and the last occurrence is \(l\). For any two chosen colors \(c\) and \(d\) with \(c < d\) (by color number), it must hold that the last occurrence of \(c\) is strictly less than the first occurrence of \(d\); that is, all the cells painted with \(c\) appear before any cell painted with \(d\).

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(k\) \((1 \le k \le n)\), representing the length of the grid and the number of colors you need to keep.
2. The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le m)\) representing the color painted in each grid cell.
3. The third line contains \(m\) integers \(b_1, b_2, \ldots, b_m\) \((1 \le b_i \le 10^9)\). Note that even if some colors do not appear in the grid, you are not allowed to choose them.

You can assume that \(m\) is at least as large as the maximum color number in the grid.

outputFormat

Output a single integer: the maximum total value you can achieve by choosing exactly \(k\) colors satisfying the non-decreasing condition after cutting. If it is impossible, output -1.

sample

5 2
1 3 2 2 3
5 10 3

15