Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

chocolate

We have a list `x1,...,xN` of pairwise different positive numbers. In one step we choose a number a from the list. We delete a and exchange for a chocolate if there is a b in the remaining list that divides a. This step can be repeated as long as we find appropriate numbers in the remaining list. What is the maximal amount of chocolate that we can get this way?

Example

```  N=9
the list: 12,5,7,8,9,3,11,2,4
12  : chocolate (divisible by 2)
5  : -
7  : -
8  : chocolate (divisible by 2)
9  : chocolate (divisible by 3)
1  : -
3  : -
11  : -
2  : -
4  : chocolate (divisible by 2)
```

Input Specification

```N
`x1 ... xN`
```

The first line is the number `1 ≤ N ≤ 105`. The second row is the members of the list separated by space. The numbers in the list are pairwise different integers between `2` and `106`

Output Specification

```M
```

A single line with the number `M`.

Sample Input 1

1. `9`
2. `12 5 7 8 9 3 11 2 4`

Sample Output 1

1. `4`
1. `9`
2. `124 58 23 38 6 7 11 13 17`
1. `0`