代码

#include<set>
#include<cstdio>
#include<algorithm>

using int64=long long;
using uchar=unsigned char;

constexpr int maxn(100000);

template<class _Tp>
	inline void chkMax(_Tp&x,const _Tp&y)
		{(x<y)&&(x=y);}

namespace IOManager{
	constexpr int FILESZ(131072);
	char buf[FILESZ];
	const char*ibuf=buf,*tbuf=buf;

	struct IOManager{
		inline char gc()
			{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

		template<class _Tp>
			inline operator _Tp(){
				_Tp s=0u;char c=gc();
				for(;c<48;c=gc());
				for(;c>47;c=gc())
					s=(_Tp)(s*10u+c-48u);
				return s;
			}
	};
}IOManager::IOManager io;

template<class _Tp,class _Tpx>
	inline void exgcd(const _Tp&x,const _Tp&y,_Tp&d,_Tpx&a,_Tpx&b){
		if(y)exgcd(y,x%y,d,b,a),b-=x/y*a;
		else a=1,b=0,d=x;
	}
inline int64 mul(const int64&x,const int64&y,const int64&p)
	{return(x*y-(int64)(((long double)x*y+0.5)/p)*p)%p;}

inline std::pair<int64,int64>EXCRT(const int&n,const int64*const&a,const int64*const&p,const int64*const&atk){
	int64 ans=0,lcmp=1,d,tx,ty,t;
	for(int i=1;i<=n;++i){
		exgcd(lcmp*atk[i],(int64)p[i],d,tx,ty);
		t=((a[i]-ans*atk[i])%p[i]+p[i])%p[i];
		if(t%d)
			return std::make_pair(-1,-1);

		ans+=mul(tx,t/d,p[i]/d)*lcmp;
		lcmp*=p[i]/d;
		ans=(ans%lcmp+lcmp)%lcmp;
	}return std::make_pair((ans+lcmp)%lcmp,lcmp);
}

int64 a[maxn+1],p[maxn+1],atk[maxn+1],pri[maxn+1];

std::multiset<int64>s;

int main(){
	for(int T=io;T;){
		const int n=io;int m=io;
		for(int i=1;i<=n;++i)
			a[i]=io;
		for(int i=1;i<=n;++i)
			p[i]=io;
		for(int i=1;i<=n;++i)
			pri[i]=io;
		for(;m;--m)
			s.insert((int)io);

		for(int i=1;i<=n;s.insert(pri[i++])){
			auto it=s.upper_bound(a[i]);
			if(it==s.begin())
				atk[i]=*it,
				s.erase(it);
			else
				atk[i]=*--it,
				s.erase(it);
		}

		int64 mx=0;
		for(int i=1;i<=n;++i)
			chkMax(mx,(a[i]+atk[i]-1)/atk[i]);

		auto ans=EXCRT(n,a,p,atk);
		if(~ans.first)
			for(;ans.first<mx;)
				ans.first+=ans.second;
		printf("%lld\n",ans.first);

		if(--T)
			s.clear();
	}

	return 0;
}

评测结果