{"raw_statement":[{"iden":"problem statement","content":"We have a directed graph $G$ with $N$ vertices numbered $1$ to $N$.\nBetween two vertices $i,j$ ($1 \\leq i,j \\leq N$, $i \\neq j$), there is an edge $i \\to j$ if and only if both of the following conditions are satisfied.\n\n*   $i<j$\n*   $\\mathrm{gcd}(i,j)>1$\n\nAdditionally, each vertex has an associated value: the value of Vertex $i$ is $A_i$.\nConsider choosing a set $s$ of vertices so that the following condition is satisfied.\n\n*   For every pair $(x,y)$ ($x<y$) of different vertices in $s$, $y$ is unreachable from $x$ in $G$.\n\nFind the maximum possible total value of vertices in $s$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^6$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"6\n1 1 1 1 1 1"},{"iden":"sample output 1","content":"4\n\nWe should choose $s={1,2,3,5}$."},{"iden":"sample input 2","content":"6\n1 2 1 3 1 6"},{"iden":"sample output 2","content":"8\n\nWe should choose $s={1,5,6}$."},{"iden":"sample input 3","content":"20\n40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3"},{"iden":"sample output 3","content":"343"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}