塔子哥有一个n个整数的数组a1,a2,...,an,他想两两将这些数字连成一张图,规则为:
从数组中选取任意两个数字ai和aj(i=j),如果ai+aj为质数,则将这两个点相连,边权即为ai+aj;
连出的图可能由若干个连通块构成,塔子哥只关心那些点数最多的连通块,他想要知道,这些连通块能构成的全部生成树中,权值最小的那棵的权值是多少。
你只需输出这棵生成树的权值。
对于一张n个节点的图,选择其中n−1条边,使得所有顶点联通,这些边一定会组成一棵树,即为这张图的一棵生成树。可以证明,图中存在至少一棵生成树。
第一行输入一个整数n(1≤n≤103)代表塔子哥拥有的数字数量。
第二行输入n个整数a1,a2,...,an(0≤ai≤106)代表塔子哥的数字。
在第一行上输出一个整数,代表在点数最多的连通块上,全部生成树中权值最小的那棵的权值。
输入
5
2 3 1 2 0
输出
10
说明
该样例连出的图如下图所示,由于仅有一个连通块,故直接输出权值最小的生成树即可。
输入
5
2 3 7 6 19
输出
5
说明
该样例连出的图如下图所示。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.