時間制限 : sec, メモリ制限 : KB
English / Japanese  

Problem J: ICPC: Ideal Coin Payment and Change

太郎君は非効率的なことが大嫌いな少年です。彼は買い物をするたびに、レジの手続きを速やかに済ませるために、お釣りの硬貨の枚数が少なくなるように代金を支払っています。

しかしある日、彼はこれが本当に効率的なのだろうかという疑問を抱きました。より多くの枚数の硬貨を支払うと、店員はその総額を計算するのにより長い時間を費やします。もしかしたら、支払う硬貨の枚数をより少なくするほうが良いのではないでしょうか?

しばらく考えて、彼は折衷案を採ることにしました。つまり、支払う硬貨の枚数とお釣りとして返される硬貨の枚数の合計が最も少なくなるように代金を支払うのです。

彼は何枚かの硬貨を持って、P 円の品物を買おうとしています。暗算が得意ではない彼のために、この最小の枚数を計算するプログラムを作成してください。

ただし、以下のことを仮定してかまいません。

  • 硬貨は 1円・5円・10円・50円・100円・500円の6種類がある。
  • 手持ちの硬貨の総額は、P 円以上である。
  • 店員は、常に最小の枚数の釣銭を返す。

Input

入力は、複数のデータセットから構成される。 一つのデータセットは、以下の形式で与えられる。

P N1 N5 N10 N50 N100 N500

Ni は、所持している i 円の硬貨の枚数を表す整数である。

P = 0 のとき、入力の終了を表す。このデータセットに対して出力をしてはならない。

Output

最小の支払う硬貨の枚数と返される硬貨の枚数の合計を1行に出力してください。

Constraints

  • データセットの数は 100 を越えない。
  • 0 ≤ Ni ≤ 1000

Sample Input

123 3 0 2 0 1 1
999 9 9 9 9 9 9
0 0 0 0 0 0 0

Output for the Sample Input

6
3