2025년 11월, 미국은 마지막 페니(1센트 동전)를 발행했습니다. 캐나다는 2012년부터 페니를 발행하지 않고 있습니다.
수십억 개의 페니가 여전히 유통되고 있지만, 페니는 시간이 지남에 따라 점차 유통에서 사라질 것으로 예상됩니다. 신용카드 거래는 센트 단위로 처리되므로, 상점들은 계속해서 상품 가격을 센트 단위로 책정할 것으로 예상됩니다. 그러나 현금 거래의 경우, 상점들은 가장 가까운 니켈(5센트) 단위로 반올림할 것으로 예상됩니다. 구체적으로, 총 구매 금액의 마지막 자리가 3, 4, 8, 9센트로 끝나면 올림 처리되고, 1, 2, 6, 7센트로 끝나면 내림 처리됩니다. 0이나 5센트로 끝나는 거래는 반올림되지 않습니다.
당신은 이것이 기회라는 것을 깨달았습니다. 현금으로 결제하면서 구매 항목을 적절하게 재배치하고 그룹화하면, 구매하는 모든 물건에 대해 약간 더 적은 금액을 지불할 수 있을지도 모릅니다! 구매하려는 각 물건의 가격(센트 단위)이 주어질 때, 모든 물건을 신용카드로 구매했을 때의 반올림되지 않은 총액과 비교하여, 현금으로만 결제하고 구매 항목을 최적으로 재배치 및 그룹화함으로써 절약할 수 있는 최대 금액을 구하십시오.
입력
첫 번째 줄에는 구매하려는 물건의 개수 $N$ ($1 \le N \le 3 \cdot 10^5$)이 주어집니다.
다음 줄에는 각 물건의 가격을 나타내는 $N$개의 정수 $p_i$ ($1 \le p_i \le 3000$)가 공백으로 구분되어 주어집니다.
출력
신용카드로 결제했을 때의 반올림되지 않은 총액과, 현금으로 결제하고 구매 항목을 최적으로 그룹화했을 때 얻을 수 있는 최저 총비용의 차이를 단일 정수로 출력하십시오.
참고
첫 번째 예제에서, 한 가지 최적의 그룹화는 다음과 같습니다. $\{78, 999, 350\}, \{59, 173, 2995, 350\}, \{882, 298\}, \{1096\}, \{497\}$.
각 그룹의 가격은 각각 1427, 3577, 1180, 1096, 497이며, 따라서 총 차이는 다음과 같습니다. $(1427 + 3577 + 1180 + 1096 + 497) - (1425 + 3575 + 1180 + 1095 + 495) = 7$.
물건들을 여러 현금 거래로 최적으로 그룹화함으로써 모든 물건을 신용카드로 결제하는 대신 7센트를 절약할 수 있습니다.
예제
예제 입력 1
11 78 59 90 999 173 882 1096 2995 298 497 350
예제 출력 1
7
예제 입력 2
2 199 299
예제 출력 2
-2