P7091 Tree on Numbers.

**This problem enables O2 optimization automatically, and the time limit is 2s.**

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$.

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

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`.

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