Description

You need to construct a binary tree whose root node has value $n$. Each node has either $2$ children or $0$ children, and it must satisfy the following rules:

• If a node has two children, then the node’s value must be equal to the product of its two children’s values.
• If a node has no children, then the node’s value must be a prime number.

You are also given $m$ constraints $a_i$, meaning that the value $a_i$ must not appear anywhere in the tree.

Your constructed binary tree must minimize the following. Let $k$ be the number of nodes: $\sum\limits_{i=1}^k\sum\limits_{j=i}^kval_{lca(i,j)}$, where $val_i$ is the value of the $i$-th node, and $lca(i,j)$ is the lowest common ancestor of nodes $i$ and $j$.

Input Format

The first line contains two positive integers $n,m$.

The next line contains $m$ numbers $a_i$.

Output Format

Output one number in a single line, the minimum value of $\sum\limits_{i=1}^k\sum\limits_{j=i}^kval_{lca(i,j)}$.

If there is no solution, output -1.

4 0

20

12 1
4

127

192 1
2

-1

Hint

Sample explanation:

Sample $1$: The optimal construction is as follows:

Here, black numbers are node values, and red numbers are node indices (you do not need to index the tree; these indices are only used to explain the sample more clearly).

$ans=val_{lca(1,1)}+val_{lca(1,2)}+val_{lca(1,3)}+val_{lca(2,2)}+val_{lca(2,3)}+val_{lca(3,3)}$

$~~~~~~~~=val_1+val_1+val_1+val_2+val_1+val_3$

$~~~~~~~~=4+4+4+2+4+2=20$

Subtask 1 (5 points): $n\leq 20$.

Subtask 2 (12 points): $n\leq 10^6$.

Subtask 3 (28 points): $n\leq 10^{12}$.

Subtask 4 (20 points): $m=0$.

Subtask 5 (35 points): $n\leq 10^{15}$.

Constraints: for all testdata, $2\leq n\leq 10^{15}$, $0\leq m\leq \min(n,10^5)$, $2\leq a_i\leq n$, and the answer does not exceed $4\times 10^{18}$.

Translated by ChatGPT 5