线段树经典运用。
设$last_i$表示上一个与$i$相同的类型。然后每次更新$[last[i]+1,i]$和$[last[last[i]]+1,last[i]]$的答案就行了。
//BZOJ 3747
//by Cydiater
//2016.10.28
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <bitset>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,typ[MAXN],hap[MAXN],last[MAXN],newpos[MAXN],L,R;
ll v,ans=0;
struct Tree{
ll delta,v;
}t[MAXN<<2];
namespace solution{
inline void reload(int root){t[root].v=max(t[root<<1].v,t[root<<1|1].v);}
void init(){
N=read();M=read();
up(i,1,N){
typ[i]=read();
last[i]=newpos[typ[i]];
newpos[typ[i]]=i;
}
up(i,1,M)hap[i]=read();
}
void downit(int root){
if(t[root].delta==0) return;
ll delta=t[root].delta;t[root].delta=0;
t[root<<1].delta+=delta;t[root<<1|1].delta+=delta;
t[root<<1].v+=delta;t[root<<1|1].v+=delta;
}
void updata(int leftt,int rightt,int root){
if(leftt!=rightt)downit(root);
if(leftt>R||rightt<L) return;
if(leftt>=L&&rightt<=R){
t[root].delta=v;
t[root].v+=v;
return;
}
int mid=(leftt+rightt)>>1;
updata(leftt,mid,root<<1);
updata(mid+1,rightt,root<<1|1);
reload(root);
}
void slove(){
up(i,1,N){
L=last[i]+1;R=i;v=hap[typ[i]];
updata(1,N,1);
if(last[i]!=0){
L=last[last[i]]+1;R=last[i];v=-hap[typ[i]];
updata(1,N,1);
}
cmax(ans,t[1].v);
}
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}