Let us always use Vertex \(1\) and ignore it below.

For integers \(x,y\) (\(x<y\)), let us consider the condition for Vertex \(y\) to be reachable from \(x\). Below, let \(f(n)\) be the smallest prime factor of \(n\).

After a case-by-case analysis based on the parities of \(x,y\), the condition can be summarized as follows.

• If \(x \equiv 0\) and \(y \equiv 0\): always reachable.
• If \(x \equiv 1\) and \(y \equiv 0\): equivalent to \(x+f(x) \leq y\).
• If \(x \equiv 0\) and \(y \equiv 1\): equivalent to \(x \leq y-f(y)\).
• If \(x \equiv 1\) and \(y \equiv 1\): equivalent to \(x+f(x) \leq y-f(y)\).

The case in which \(x \equiv 0\) and \(y \equiv 0\) is obvious. We will explain the remaining cases.

First, the smallest integer reachable from \(x\) is \(x+f(x)\). Here, \(x+f(x)\) is always even, from which the above condition for the case in which \(x \equiv 1\) and \(y \equiv 0\) is derived.

Similarly, the largest integer from which \(y\) is reachable is \(y-f(y)\), which is always even, so the case in which \(x \equiv 0\) and \(y \equiv 1\) is also resolved.

Let us consider the last case. Since it is obvious that the condition above is necessary, we will prove the sufficiency. Assume that \(y\) is reachable from \(x\) while the condition is not satisfied. If \(y\) was reachable from \(x\) via two or more transitions, the condition would hold, so we only have to consider the direct transition \(x \to y\). Let \(p\) be a common prime factor of \(x,y\). If we write \(x=ap,y=bp\), \(a\) and \(b\) are both odd. Thus, we have \(x=ap<(a+1)p<bp=y\), which means \(y\) is reachable from \(x\) via two transitions. Thus, \(x+f(x) \leq y-f(y)\) must eventually hold, which completes the proof.

For an integer \(n\), let us define \(l(n),r(n)\) as follows.

• \(l(n)=n,r(n)=n+1\) (\(x \equiv 0 \mod 2\))
• \(l(n)=x-f(n)+1,r(n)=x+f(n)\) (\(x \equiv 1 \mod 2\))

Then, for integers \(x,y\) (\(x \neq y\)), \(x\) and \(y\) are unreachable from each other if and only if the intervals \([l(x),r(x))\) and \([l(y),r(y))\) intersect.

Let us return to the original problem. If the chosen set of vertices satisfies the condition in the problem statement, there must be a point contained in all intervals corresponding to the vertices. Thus, the problem can eventually be solved by adding \(A_i\) to the interval \([l(i),r(i))\) for each \(2 \leq i \leq N\) and finding the max among all values.

Our solution runs in \(O(N)\) time.

Sample submission (c++)