5 \(s / 768\) \(MB / 140\) points

Little Daniel has a bag of candy and \(N\)

cards.

Each of the cards has a positive integer \(P\)

\(i\)

written on it. While Daniel was eating his candy,
he thought of a fun game. He can tie together two cards with labels \(a\)

and \(b\)

, and then he
must eat min(P

\(a\)

% P

\(b\)

, P

\(b\)

% P

\(a\)

)

of candy, where operation x % y

denotes the remainder
when dividing x with y.

He wants to tie together pairs of cards in a way that, when he lifts one of them, all the rest
are also lifted up. Each card can be directly connected with a tie to any number of other
cards. As Daniel is watching his figure, he doesn’t want to consume too much, so he is
asking you to calculate the minimal number of candy he must eat so all cards are connected.

In test cases worth 30% of total points, it will hold

10 .
\(N\) ≤
^{3}
In test cases worth 40% of total points, it will hold

10 .
\(P\) \(i\) ≤
^{6}
In test cases worth 70% of total points, at least one of the two conditions will hold.

The first line of input contains the positive integer \(N\)

. 1
\(N\)
10 )
(
≤
≤
^{5}
Each of the following \(N\)

lines contains a positive integer P {i}{ }
.
1
\(P\)
10 )
(
≤
\(i\) ^{≤}
^{7}

The first and only line of output must contain the required value from the task.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 6