#P3158. 千钧一发

    ID: 2334 传统题 1000ms 512MiB 尝试: 2302 已通过: 637 难度: 6 上传者: 标签>CF2100提高最大权独立集二分图建模奇偶性分析欧几里得算法补集转化顶点覆盖最小割建模Dinic最大流最小割定理

千钧一发

题目背景

在你正确回答表达式的值以后,石板又出现了新的状况﹐然而这次情况十分紧急,如果无法做出正确的选择,Katherine 皇后很可能再也无法和 Kanari 国王在一起了。

题目描述

石板上突然出现 nn 个奇怪的装置,Kanari 国王仔细观察发现每个装置上面都写有两个正整数,我们记第 ii 个装置上的两个正整数分别为 aia_i 和 bib_i 。其中 aia_i 表示这个装置的特征值,bib_i 表示这个装置蕴含的能量值。现在请你在这 nn 个装置中选择一部分出来,使得选择的任意两个装置 ii 和 j(i≠j)j(i\neq j)至少满足下面两个条件之一:

  1. 不存在正整数 TT 使得 ai2+aj2=T2a_i^2+a_j^2=T^2
  2. aia_i和 aja_j 有大于 11 的公因子。

你的目标就是使得选出来装置的能量值总和最大,如果你回答正确,说不定石板会按照它所说的,将 Katharon 国最珍贵的财产交出来,否则国王,皇后以及你的小命都将难保。

输入格式

第一行一个正整数 nn 。

第二行共包括 nn 个正整数,第 ii 个正整数表示 aia_i 。

第三行共包括 nn 个正整数,第 ii 个正整数表示 bib_i 。

输出格式

共一行,包括一个正整数,表示在合法的选择条件下,可以获得的能量值总和的最大值。

样例输入

4
3 4 5 12
9 8 30 9

样例输出

39

数据规模与约定

1≤n≤103,1≤ai,bi≤106 1\le n \le 10^3,1\le a_i,b_i\le 10^6

题目来源

Katharon+#1