500엔 저금

일본에서 널리 알려진 저축 방법 중 하나가 500엔 저금이다. 방법은 간단하다. 물건을 사고 받은 거스름돈에 500엔 동전이 있으면 그 동전을 저금통에 넣는다. 보통 10년이면 저금통에 100만 엔이 넘게 쌓인다.

500엔 저금에 열심인 사람은 500엔 동전을 되도록 많이 받으려고 1000엔 지폐와 손에 있는 동전을 골라서 낸다. 예를 들어 817엔을 낼 때 1320엔(1000엔 지폐 한 장, 100엔 동전 세 개, 10엔 동전 두 개)을 건네면 거스름돈으로 500엔 동전 한 개와 1엔 동전 세 개를 받는다.

당신의 친구도 그런 사람이다. 그는 여행을 계획하면서 길에 있는 기념품 가게 여러 곳을 들르려고 한다. 가게는 계획한 순서대로 한 곳씩 방문하고, 순서는 바꿀 수 없다. 가게마다 기념품을 한 종류만 팔고, 그는 모든 가게의 가격을 미리 알고 있다. 각 가게에서 기념품을 최대 한 개까지 살 수 있고, 이렇게 500엔 동전을 최대한 많이 모으려고 한다. 출발할 때 1000엔 지폐는 넉넉히 있고 동전은 하나도 없다. 모으는 500엔 동전 개수가 같다면 지출을 최대한 줄이려고 한다.

지불 규칙은 다음과 같다. 손에 있는 1엔, 5엔, 10엔, 50엔, 100엔 동전을 원하는 만큼 낼 수 있고, 1000엔 지폐도 원하는 만큼 낼 수 있다. 500엔 동전은 저금통으로 들어가므로 지불에 쓰지 않는다. 가게는 낸 금액에서 가격을 뺀 차액을 정확히 거슬러 주고, 거스름돈은 1엔, 5엔, 10엔, 50엔, 100엔, 500엔 동전과 1000엔 지폐를 써서 개수가 가장 적어지도록 구성한다. 가게의 잔돈은 충분하다. 딱 맞는 금액을 낼 수 있어도 원하는 동전을 받기 위해 가격보다 많은 금액을 내도 된다. 1000엔짜리 기념품을 살 때 1000엔 지폐 한 장과 100엔 동전 다섯 개를 내면 500엔 동전 한 개를 받는다. 다만 동전을 너무 많이 내면 오히려 손해다. 같은 1000엔짜리 기념품에 100엔 동전 열 개와 1000엔 지폐 한 장을 내면 500엔 동전 두 개가 아니라 1000엔 지폐 한 장을 돌려받는다.

거스름돈이 항상 정확하므로, 지출은 그가 산 기념품 가격의 합이다.

가격이 800엔, 700엔, 1600엔, 600엔인 가게를 이 순서로 방문하는 경우를 보자. 이때 500엔 동전은 최대 두 개까지 모을 수 있고, 두 개를 모으는 데 드는 최소 지출은 2900엔이다. 첫 가게를 건너뛰고 두 번째 가게에서 700엔을 낼 때 1000엔 지폐 한 장을 내면 100엔 동전 세 개를 받는다. 다음 가게에서 1600엔짜리를 살 때 그 100엔 동전 하나와 1000엔 지폐 두 장을 내면 500엔 동전 한 개를 받는다. 마지막 가게에서도 같은 방법으로 500엔 동전 한 개를 더 받는다. 첫 가게에서 사면서 500엔 동전 두 개를 모을 수도 있지만, 그러면 1600엔짜리와 600엔짜리를 모두 사야 해서 지출이 3000엔 이상이 된다.

방문 순서대로 기념품 가격이 주어진다. 여행 동안 모을 수 있는 500엔 동전의 최대 개수와 그 개수를 모으는 데 드는 최소 지출을 구하는 프로그램을 작성하라.

입력은 데이터 세트 최대 50개로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

n
p1
...
pn

$n$은 기념품 가게의 수이고 100 이하의 양의 정수다. $p_i$는 $i$번째 가게가 파는 기념품의 가격이고 5000 이하의 양의 정수다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

데이터 세트마다 두 정수 $c$와 $s$를 공백으로 구분해 한 줄에 출력한다. $c$는 여행 동안 모을 수 있는 500엔 동전의 최대 개수이고, $s$는 500엔 동전 $c$개를 모으는 데 드는 최소 지출이다.