题目背景
xtq 在小学四年级的时候得到了一套神奇的画笔。为了测试神笔的威力(以及展现自己过人的艺术天赋),他决定先为美术老师临摹几幅画。
题目描述
每幅画的形态可以抽象为排成一列的 n 个格子,其中第 i 个格子具有一个权值 ai。
xtq 有足够多不同颜色的画笔,每当他使用一根笔,他可以在格子上画下至少长度为 k 的连续一段,然后再换另一根笔从下一个格子继续画,其中 k<n。
美术老师为了考验 xtq 的绘画功力,为他设置了一些挑战。
他可以从 1 到 k 的任意一个格子开始画到编号为 n 的格子,其中从第 i 个格子开始会获得 bi 的得分。
假设 xtq 使用同一根画笔,从编号为 i 的格子连续地画到编号为 j 的格子,他就会获得(aiorai+1orai+2or⋯oraj)+(aiandai+1andai+2and⋯andaj)+gcd(ai,ai+1,ai+2,…,aj) 的分数,其中 gcd 代表最大公约数。
现在,xtq 希望找到一种安排画笔使用的方案,使得对于每一幅需要临摹的画,他总共获得的分数尽量多。
输入格式
第一行,一个正整数 T,表示画的数量。
对于每一幅画:
第一行,两个正整数 n,k。
第二行,n 个正整数 a1,a2,a3,…,an。
第三行,k 个整数 b1,b2,b3,…,bk。
输出格式
对于每一幅画,输出一个整数,代表 xtq 完成这幅画最多能获得的分数。
提示
样例解释:
xtq 可以从 1 开始,获得 6 分初始得分;第一段画 [1,2],获得 5 分;第二段画 [3,4],获得 10 分;第三段画 [5,6],获得 10 分。共 31 分。
对于 20% 的数据,n≤10。
对于 40% 的数据,n≤3000。
对于 70% 的数据,n≤30000。
对于 100% 的数据,1≤k<n≤3×105,T≤10,1≤ai≤230,−230≤bi≤230。
数据有梯度,应该不太卡常。