const int N=5005;
const ll Inf=0x3f3f3f3f3f3f3f3f;
int n,m,x[N];
ll a[N],c[N],dp[N][N],dp1[N][N];
void dp2(int l,int r)
{
	int k=r-l+1;ll mi[N][N];
	for(int i=1;i<=k;i++)
		for(int j=i;j<=k;j++)
		{
			if(i==j)mi[i][j]=c[l+i-1];
			else mi[i][j]=min(mi[i][j-1],c[l+j-1]);
//			cout<<"mi["<<i<<"]["<<j<<"]="<<mi[i][j]<<" ";
		}
	for(int i=0;i<=k;i++)
		for(int j=0;j<=k;j++)dp1[i][j]=Inf;
	dp1[0][0]=0;
	for(int i=1;i<=k;i++)
		for(int j=0;j<=i;j++)
		{
			if(i<k)dp1[i][j]=dp1[i-1][j];
			if(j)dp1[i][j]=min(dp1[i][j],dp1[i-1][j-1]+mi[i-j+1][i]+a[l+i-1]);
		}
}
void Solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=m;i++)cin>>x[i];
	dp2(1,n);
	//  for(int i=1;i<=n;i++)
	//  {
	//  	for(int j=0;j<=i;j++)
	// 		cout<<"dp1["<<i<<"]["<<j<<"]="<<dp1[i][j]<<' ';
	//  	cout<<endl;
	//  }
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=m;i++)
	{
		dp2(x[i-1]+1,x[i]);
		for(int j=i;j<=x[i];j++)
		{
			for(int p=1;p<=x[i]-x[i-1];p++)
				dp[i][j]=min(dp[i][j],dp[i-1][j-p]+dp1[x[i]-x[i-1]][p]);
		}
	}
	ll ans=Inf;
	for(int i=m;i<=n;i++)ans=min(ans,dp[m][i]);
	cout<<ans<<endl;
}

WA on sample 2:expected 533,found 751