500-Yen Saving

One well known way to save money in Japan is the 500-yen saving. The method is simple. Whenever a 500-yen coin comes back in the change of a purchase, you drop that coin into a saving box. Ten years of this usually leaves more than one million yen in the box.

People who take the 500-yen saving seriously pick which 1000-yen bills and coins to hand over so that they receive as many 500-yen coins as possible. To pay 817 yen, for example, you hand over 1320 yen (one 1000-yen bill, three 100-yen coins and two 10-yen coins) and receive one 500-yen coin and three 1-yen coins in the change.

A friend of yours is one of these savers. He is planning a sightseeing trip and wants to visit a number of souvenir shops along his way. He visits the shops one by one in the planned order, and the order cannot be changed. Every shop sells one kind of souvenir, and he knows the price at every shop. He buys at most one souvenir at each shop and wants to collect as many 500-yen coins as possible this way. On his departure he carries enough 1000-yen bills and no coins at all. Among the plans that collect the same number of 500-yen coins, he wants to spend as little as possible.

The payment rules are these. He can hand over any number of the 1-yen, 5-yen, 10-yen, 50-yen and 100-yen coins he holds, together with any number of 1000-yen bills. A 500-yen coin goes into the saving box, so he never spends one. The shop returns the exact change, that is the difference between the amount handed over and the price, and composes the change from 1-yen, 5-yen, 10-yen, 50-yen, 100-yen and 500-yen coins and 1000-yen bills using the smallest possible number of pieces. The shop has enough coins. He may hand over more than the price even when he can pay the exact amount, in order to receive the coins he wants. Buying a souvenir of 1000 yen, he can hand over one 1000-yen bill and five 100-yen coins and receive one 500-yen coin. Using too many coins does no good. For the same 1000-yen souvenir, handing over ten 100-yen coins and one 1000-yen bill gives back one 1000-yen bill, not two 500-yen coins.

Because the change is always exact, his expenses are the sum of the prices of the souvenirs he buys.

Consider visiting shops whose souvenir prices are 800 yen, 700 yen, 1600 yen and 600 yen, in this order. He can collect at most two 500-yen coins, and the least he can spend for two coins is 2900 yen. He skips the first shop, then pays 700 yen at the second shop with a single 1000-yen bill and receives three 100-yen coins. At the next shop he hands over one of these 100-yen coins and two 1000-yen bills for the 1600-yen souvenir, and receives one 500-yen coin. The last shop gives him another 500-yen coin in the same way. He can also collect two 500-yen coins while buying at the first shop, but then he has to buy both the 1600-yen and the 600-yen souvenirs, so his expenses are at least 3000 yen.

You are given the souvenir prices in the order of the visits. Write a program that finds the maximum number of 500-yen coins he can collect during the trip, and the minimum expenses needed to collect that many coins.

The input consists of at most 50 datasets. Each dataset has the following format.

n
p1
...
pn

$n$ is the number of souvenir shops, a positive integer not greater than 100. $p_i$ is the price of the souvenir sold at the $i$-th shop, a positive integer not greater than 5000.

The end of the input is a line with a single zero.

For each dataset, print two integers $c$ and $s$ on one line, separated by a space. $c$ is the maximum number of 500-yen coins he can collect during the trip, and $s$ is the minimum expenses needed to collect $c$ coins.