0038 - 500円玉貯金

日本の有名な貯金手法のひとつとして 500 円玉貯金が知られている．方法は簡単で，買い物のお釣りに 500 円玉があったらそれを貯金箱に入れるだけだ．通常，10 年もすれば貯金箱に 100 万円貯まっているだろう．

世の中には 500 円玉貯金に積極的な人々がいる．彼らは，買い物の際に 1000 円札と小銭をうまく出すことによって 500 円玉を効率よく得られるように努力している．例えば，817 円の支払いに 1320 円（1000 円札 1 枚，100 円玉 3 枚，10 円玉 2 枚）を出すことで，お釣りとして 500 円玉 1 枚（と 1 円玉 3 枚）が手に入る．

君の友達も 500 円玉貯金にとり憑かれたひとりだ．彼は観光のための旅に出かけようとしており，その道中にいくつかの土産物屋を順に訪れることを計画している．これらの土産物屋には各店に土産物が 1 種類ずつあり，彼はそれらの値段のリストを持っている．彼は，これらの土産物をうまく買い，500 円玉を 1 枚でも多く手に入れたいと考えている．ただし，各店では土産物を高々ひとつしか買わない．旅に出る時点で，彼は十分な 1000 円札を持っているが小銭は全く持っていない．また，土産物屋を訪れる順番は変えられない．同じ枚数の 500 円玉を手に入れられるならば，彼はなるべく使うお金を減らしたいと考えている．

例えば，これから訪れる土産物屋での土産物の値段が順に 800 円，700 円，1600 円，600 円だったとしよう．この場合に手に入る 500 円玉の最大枚数は 2 枚であり，その 2 枚を得るのに必要な最低限の出費は 2900 円である．最初の 800 円の土産物を買わず，次の店で 700 円の土産物を 1000 円札で買って 100 円玉 3 枚を手に入れ，その後に残りのふたつを 2100 円と 1100 円を出して買うことで，500 円玉を 2 枚手に入れられる．仮に最初の 800 円の土産物を買ったとすると，500 円玉を 2 枚手に入れるためには少なくとも 1600 円と 600 円の土産物を買わねばならず，結局 3000 円以上の出費となってしまう．

君は彼に，彼の目的を助けるためのプログラムの作成を頼まれた．土産物屋を訪れる順に書かれた土産物の値段のリストを受け取り，最大何枚の 500 円玉を得られるか，及びその枚数を得るのに最低限何円使わなければならないかを答えるプログラムを作って欲しい．

それぞれの支払いに使用できるのは，その時点で持っている 1 円玉，5 円玉，10 円玉，50 円玉，100 円玉の小銭及び（充分にある）1000 円札だけである．支払いの際には，これらの小銭や 1000 円札をいくら出しても構わない．一方，お店は，お釣り，すなわち出されたお金と土産物の価格の差額を，その金額を構成する最小枚数の，1 円玉，5 円玉，10 円玉，50 円玉，100 円玉，500 円玉，及び 1000 円札で返す．無駄な小銭を出して支払いをすることは自由であり，例えば，1000 円の土産物を買う際に 1000 円札と共に 5 枚の 100 円玉を出すことで，お釣りとして 500 円玉を 1 枚手に入れることも可能である．しかし，欲張って小銭を多く出しすぎるのも良くない．1000 円の土産物を買うのに，1000 円札と共に 100 円玉を 10 枚出したとしても，お店は 1000 円札 1 枚を返してくれるだけで 500 円玉 2 枚は手に入らない．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

n
p₁
...
p_n

n は土産物屋の数であり，100 を超えない正の整数である．p_i は i 番目の土産物屋の土産物の値段である．p_i は，正の整数であり，5000 を超えない．

入力の終わりは，ゼロをひとつ含むだけの行で表される．

各データセットについて、ふたつの整数 c と s をひとつの空白文字で区切って 1 行に出力せよ．c は手に入る 500 円玉の最大枚数であり，s はその枚数の 500 円玉を得るのに必要な土産物の購入金額の合計の最小値である．

4
800
700
1600
600
4
300
700
1600
600
4
300
700
1600
650
3
1000
2000
500
3
250
250
1000
4
1251
667
876
299
0

2 2900
3 2500
3 3250
1 500
3 1500
3 2217