#P3275. Number

Number

Number

题目描述

给定 nn 个正整数。你可以选取其中若干个数,要求任何两个被选的数 a,ba,b 都不会同时满足下列两个条件。

  1. 存在正整数 cc 使 a2+b2=c2a^2+b^2=c^2。
  2. gcd⁡(a,b)=1\gcd(a,b)=1。

求选出的数之和的最大值。

输入格式

第一行一个正整数 nn。第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一行一个整数,表示最大和。

样例

5
3  4 5 6 7
22

数据规模与约定

1≤n≤30001\le n\le3000。

BZOJ 归档题面