UOJ Logo Sharp Sword 剑锋 OI

SSOI

#1091. QSC and Master 【剑锋OI#Ⅱ期#秩序团#模拟赛#20180325#011】

统计

时间限制:1S / 空间限制:256MB

【问题描述】

  给定N对数字对,每对包含key和value,现在你需要通过移除某些数字对来获取得分。你可以移除两个连续的数字对,仅当这两个数字对的key值非互质(gcd不是1),你可以得到这两个数字对的value值作为得分。
  请问你最多可以得到多少得分。

【输入格式】

第一行,一个整数T(1≤T≤10) ,表示有T组测试数据;
对于每组测试数据:
第一行,一个整数N;
第二行,N个整数,表示key值;
第三行,N个整数,表示value值。

【输出格式】

T行,对于每组测试数据输出一个最大得分。

【输入样例1】

3
3
1 2 3
1 1 1
3
1 2 4
1 1 1
4
1 3 4 3
1 1 1 1

【输出样例1】

0
2
0

【数据范围】

1≤N≤300
1≤Ai.key≤1,000,000,000
0<Ai.value≤1,000,000,000

【题目来源】

HDU5900