[POI 2015 R1] 影迷 Movie-goer

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

共有 $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$ 个整数 $f_1,f_2,\ldots,f_n$。

第三行输入 $m$ 个整数 $w_1,w_2,\ldots,w_m$。

输出格式

输出一行一个整数，表示可以获得的最大好看值总和。

样例输入 1

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

样例输出 1

15

数据范围

对于所有数据，保证 $1\le m\le n\le 10^6$，$1\le f_i\le m$，$1\le w_i\le 10^6$。