Problem Background

This problem automatically enables O2 optimization with a time limit of 2 seconds.

Problem Description

You need to construct a binary tree where the root node has a value of $n$. Each node has either $2$ or $0$ children, and the following constraints must be met:

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

Additionally, you will be given $m$ restrictions $a_i$, indicating that the value $a_i$ cannot appear in the tree.

Your constructed binary tree should minimize the sum $\sum\limits_{i=1}^k\sum\limits_{j=i}^k val_{lca(i,j)}$, where $k$ is the number of nodes, $val_i$ represents the value of the $i$-th node, and $lca(i,j)$ denotes the lowest common ancestor of nodes $i$ and $j$.

Input Format

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

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

Output Format

Output a single number, which is the minimum value of $\sum\limits_{i=1}^k\sum\limits_{j=i}^k val_{lca(i,j)}$.

If there is no solution, output -1.

Sample Input and Output

Sample Input #1

4 0

Sample Output #1

20

Sample Input #2

12 1
4

Sample Output #2

127

Sample Input #3

192 1
2

Sample Output #3

-1

Notes

Sample Explanation:

Sample #1: The optimal solution is as follows:

In this diagram, black numbers represent values, and red numbers represent labels (you do not need to label the tree; the labels are only for easier explanation of the sample).

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

For all data, $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}$.

见题面 Input 部分

见题面 Output 部分