P3582 [POI 2015 R1] Movie-goer

There are $m$ movies, numbered $1, 2, \ldots, m$. The $i$-th movie has value $w_i$. Over $n$ days, exactly one movie is shown per day; on day $i$, movie $f_i$ is shown. You may choose $l, r$ ($1 \le l \le r \le n$) and watch all movies shown on days $l, l+1, \ldots, r$. However, if you watch the same movie more than once, you get bored and therefore cannot obtain this movie’s value. Now you need to maximize the total value of the movies that are watched exactly once.

The first line contains two integers $n, m$. The second line contains $n$ integers; the $i$-th is $f_i$. The third line contains $m$ integers; the $i$-th is $w_i$.

Print one integer, the maximum possible sum of values of movies watched exactly once.

Constraints For $100\%$ of the testdata, $1 \le m \le n \le 10^6$, $1 \le f_i \le m$, and $1 \le w_i \le 10^6$. ---- Original problem name: Kinoman. Translated by ChatGPT 5