CF1630D Flipping Range

#include <bits/stdc++.h>
using namespace std;
long long a[1000001];
long long dp[1000001][2];
long long n,m;
int t;
long long len;
long long gcd(long long a,long long b){
	if(a<b)return gcd(b,a);
	if(a%b==0)return b;
	return gcd(b,a-b);
}
int main()
{
	int t;cin>>t;
	while(t--){
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
		for(int i=1;i<=m;i++){
			long long tmp;scanf("%lld",&tmp);
			if(i==1)len=tmp;
			else len=gcd(tmp,len);
		}
		for(int i=0;i<len;++i)dp[i][0]=0,dp[i][1]=-1e16;
		for(int i=0;i<n;++i){
			long long v=a[i+1];
			long long pos=i%len;
			long long v0=max(dp[pos][1]-v,dp[pos][0]+v);
			long long v1=max(dp[pos][0]-v,dp[pos][1]+v);
			dp[pos][0]=v0;
			dp[pos][1]=v1;
		}
		long long sum0=0,sum1=0;
		for(int i=0;i<len;++i)sum0+=dp[i][0],sum1+=dp[i][1];
		printf("%lld\n\n",max(sum0,sum1));
	}
}