En novembre 2025, les États-Unis ont frappé leurs dernières pièces d'un cent. Le Canada n'a plus frappé de pièces d'un cent depuis 2012.

Des milliards de pièces d'un cent restent en circulation, mais elles sont destinées à disparaître progressivement. Les magasins devraient continuer à fixer les prix des articles au cent près, car les transactions par carte de crédit sont traitées au cent près. Cependant, pour les transactions en espèces, les magasins sont censés arrondir au nickel (cinq cents) le plus proche. Plus précisément, si le dernier chiffre du total d'un achat se termine par 3, 4, 8 ou 9 cents, le total sera arrondi au supérieur ; s'il se termine par 1, 2, 6 ou 7 cents, il sera arrondi à l'inférieur. Les transactions se terminant par 0 ou 5 cents ne sont pas arrondies.

Vous réalisez que cela représente une opportunité. Si vous payez en espèces et que vous réorganisez et regroupez vos achats de manière appropriée, vous pourriez payer un peu moins cher pour tout ce que vous achetez ! Étant donné les prix des articles individuels que vous souhaitez acheter en cents, déterminez le montant maximum que vous pourriez économiser en payant uniquement en espèces et en réorganisant et regroupant vos achats de manière optimale, par rapport au prix total non arrondi que vous paieriez si vous achetiez tous les articles avec une carte de crédit.

Entrée

La première ligne de l'entrée contient un entier unique $N$ ($1 \le N \le 3 \cdot 10^5$), le nombre d'articles que vous avez l'intention d'acheter.

La ligne suivante contient $N$ entiers séparés par des espaces $p_i$ ($1 \le p_i \le 3000$), les prix des articles en cents.

Sortie

Affichez un entier unique : la différence entre le prix total par carte de crédit sans arrondi et le coût total le plus bas pouvant être obtenu en payant en espèces et en regroupant les achats de manière optimale.

Remarque

Pour le premier échantillon, un regroupement optimal des articles est $\{78, 999, 350\}, \{59, 173, 2995, 350\}, \{882, 298\}, \{1096\}, \{497\}$.

Les prix de chaque groupe sont, respectivement, 1427, 3577, 1180, 1096, 497 et donc la différence totale est $(1427 + 3577 + 1180 + 1096 + 497) - (1425 + 3575 + 1180 + 1095 + 495) = 7$.

Vous économisez 7 cents en regroupant de manière optimale les articles en plusieurs transactions en espèces au lieu de tout payer avec une carte de crédit.

Exemples

Entrée 1

11
78 59 90 999 173 882 1096 2995 298 497 350

Sortie 1

7

Entrée 2

2
199 299

Sortie 2

-2