Nier

题号：NC25341
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一张大小为N的无向图，每个点都有一个点权 $A_i$ ，权值各不相同。( $N\le20000,A_i\le10^5$ )

对于两个点X,Y。只有当 $gcd(A_x,A_y)=min(A_x,A_y)$ ，并且 $\frac {max(A_x,A_y)}{min(A_x,A_y)}$ 是一个质数，这样的两个点我们才连边。

求这个图的最小点权覆盖。（对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。最小点权覆盖就是其中点的权值总和最小的S集合。）

输入描述:

第一行一个正整数N，表示图的大小。

第二行N个正整数表示每个点的点权。

输出描述:

输出一行一个整数，表示答案。

示例1

输入

复制

5
1 2 3 4 5

输出

复制

说明

可以看出和1连边的只有2，3，5。

可以看出和2连边的只有1，4。

可以看出和3连边的只有1。

可以看出和4连边的只有2。

可以看出和5连边的只有1。

因此选择1和2这两个点，答案是最优的。