[POI2015] KIN

题目描述

共有 $m$ 部电影,编号为 $1,2,\ldots,m$,第 $i$ 部电影的好看值为 $w_i$。 在 $n$ 天之中,每天会放映一部电影,第 $i$ 天放映的是第 $f_i$ 部。 你可以选择 $l,r$($1\le l\le r\le n$),并观看第 $l,l+1,\ldots,r$ 天内所有的电影。 但如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。 现在,您需要最大化观看且仅观看过一次的电影的好看值的总和。

输入输出格式

输入格式


第一行两个整数 $n,m$。 第二行包含 $n$ 个整数,第 $i$ 个表示 $f_i$。 第三行包含 $m$ 个整数,第 $i$ 个表示 $w_i$。

输出格式


一行一个整数,表示仅观看过一次的电影的好看值的总和的最大值。

输入输出样例

输入样例 #1

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

输出样例 #1

15

说明

**【数据范围】** 对于 $100\%$ 的数据,$1\le m\le n\le 10^6$,$1\le f_i\le m$,$1\le w_i\le 10^6$。 ---- 原题名称:Kinoman。