output_description: For each dataset, print a line containing two integers _c_ and _s_ separated
  by a space. Here, _c_ is the maximum number of 500-yen coins that he can get
  during his trip, and _s_ is the minimum expenses that he need to pay to get
  _c_ 500-yen coins.
input_description: The input consists of at most 50 datasets, each in the following format.
  
  > _n_  
  >  _p_ 1  
  >  ...  
  >  _p n_  
  >
  
  _n_ is the number of souvenir shops, which is a positive integer not greater
  than 100. _p i_ is the price of the souvenir of the _i_ -th souvenir shop. _p
  i_ is a positive integer not greater than 5000.
  
  The end of the input is indicated by a line with a single zero.
attempt: def compute_max_num_500_coins(prices):
      num_500_coins = 0
      coin = 0
      possible_thousand_coin_prices = []
      for p in prices:
          if p % 1000 == 0:
              if coin >= 500:
                  possible_thousand_coin_prices.append(p)
          elif p % 1000 <= 500:
              num_500_coins += 1
              coin += 500 - p % 500
          elif p % 500 <= coin:
              num_500_coins += 1
              coin -= p % 500
          else:
              coin += 500 - p % 500
  
      thousand_coin_price = 0
      if len(possible_thousand_coin_prices) > 0 and coin >= 500:
          thousand_coin_price = min(possible_thousand_coin_prices)
          num_500_coins += 1
          coin -= 500
      return num_500_coins, coin, thousand_coin_price
  
  
  def find_unneeded_prices(prices, remaining_coin):
      table = []
      for i in range(len(prices) + 1):
          table.append([0] * (remaining_coin + 1))
      for i in range(1, len(prices) + 1):
          p = prices[i - 1]
          prev_row = table[i - 1]
          row = table[i]
          for j in range(remaining_coin + 1):
              r = 500 - p % 500
              if j < r:
                  row[j] = prev_row[j]
              else:
                  row[j] = max(prev_row[j], prev_row[j - r] + p)
      i = len(prices)
      j = remaining_coin
      unneeded_prices = []
      while i > 0 and j > 0:
          if table[i][j] > table[i - 1][j]:
              j -= 500 - prices[i - 1] % 500
              unneeded_prices.append(prices[i - 1])
          i -= 1
      return unneeded_prices
  
  
  while True:
      n = int(input())
      if n == 0:
          break
      prices = []
      for i in range(n):
          prices.append(int(input()))
      no_thousand_prices = [p for p in prices if p % 1000 != 0]
      max_num_500_coins, remaining_coin, thousand_coin_price = compute_max_num_500_coins(
          prices
      )
      target_prices = [p for p in prices if p % 1000 > 500]
      unneeded_prices = find_unneeded_prices(target_prices, remaining_coin)
      expense = sum(no_thousand_prices) - sum(unneeded_prices) + thousand_coin_price
      print(max_num_500_coins, expense)
  
problem_description: 500-yen Saving
  
  "500-yen Saving" is one of Japanese famous methods to save money. The method
  is quite simple; whenever you receive a 500-yen coin in your change of
  shopping, put the coin to your 500-yen saving box. Typically, you will find
  more than one million yen in your saving box in ten years.
  
  Some Japanese people are addicted to the 500-yen saving. They try their best
  to collect 500-yen coins efficiently by using 1000-yen bills and some coins
  effectively in their purchasing. For example, you will give 1320 yen (one
  1000-yen bill, three 100-yen coins and two 10-yen coins) to pay 817 yen, to
  receive one 500-yen coin (and three 1-yen coins) in the change.
  
  A friend of yours is one of these 500-yen saving addicts. He is planning a
  sightseeing trip and wants to visit a number of souvenir shops along his way.
  He will visit souvenir shops one by one according to the trip plan. Every
  souvenir shop sells only one kind of souvenir goods, and he has the complete
  list of their prices. He wants to collect as many 500-yen coins as possible
  through buying at most one souvenir from a shop. On his departure, he will
  start with sufficiently many 1000-yen bills and no coins at all. The order of
  shops to visit cannot be changed. As far as he can collect the same number of
  500-yen coins, he wants to cut his expenses as much as possible.
  
  Let's say that he is visiting shops with their souvenir prices of 800 yen, 700
  yen, 1600 yen, and 600 yen, in this order. He can collect at most two 500-yen
  coins spending 2900 yen, the least expenses to collect two 500-yen coins, in
  this case. After skipping the first shop, the way of spending 700-yen at the
  second shop is by handing over a 1000-yen bill and receiving three 100-yen
  coins. In the next shop, handing over one of these 100-yen coins and two
  1000-yen bills for buying a 1600-yen souvenir will make him receive one
  500-yen coin. In almost the same way, he can obtain another 500-yen coin at
  the last shop. He can also collect two 500-yen coins buying at the first shop,
  but his total expenditure will be at least 3000 yen because he needs to buy
  both the 1600-yen and 600-yen souvenirs in this case.
  
  You are asked to make a program to help his collecting 500-yen coins during
  the trip. Receiving souvenirs' prices listed in the order of visiting the
  shops, your program is to find the maximum number of 500-yen coins that he can
  collect during his trip, and the minimum expenses needed for that number of
  500-yen coins.
  
  For shopping, he can use an arbitrary number of 1-yen, 5-yen, 10-yen, 50-yen,
  and 100-yen coins he has, and arbitrarily many 1000-yen bills. The shop always
  returns the exact change, i.e., the difference between the amount he hands
  over and the price of the souvenir. The shop has sufficient stock of coins and
  the change is always composed of the smallest possible number of 1-yen, 5-yen,
  10-yen, 50-yen, 100-yen, and 500-yen coins and 1000-yen bills. He may use more
  money than the price of the souvenir, even if he can put the exact money, to
  obtain desired coins as change; buying a souvenir of 1000 yen, he can hand
  over one 1000-yen bill and five 100-yen coins and receive a 500-yen coin. Note
  that using too many coins does no good; handing over ten 100-yen coins and a
  1000-yen bill for a souvenir of 1000 yen, he will receive a 1000-yen bill as
  the change, not two 500-yen coins.
samples: [{"input": "800\n    700\n    1600\n    600\n    4\n    300\n    700\n    1600\n    600\n    4\n    300\n    700\n    1600\n    650\n    3\n    1000\n    2000\n    500\n    3\n    250\n    250\n    1000\n    4\n    1251\n    667\n    876\n    299\n    0", "output": "2900\n    3 2500\n    3 3250\n    1 500\n    3 1500\n    3 2217"}]