No.158 奇妙なお使い

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 59
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 125 / 出題時の順位表

問題文

A君は1000円札を$A_{1000}$枚、100円玉を$A_{100}$枚、1円玉を$A_{1}$枚持っている。
Bさんのところで紙幣、硬貨の種類を問わずちょうど$D_b$円払うと、($D_b$円より多く払うことは出来ない)
1000円札を$B_{1000}$枚、100円玉を$B_{100}$枚、1円玉を$B_{1}$枚もらえる。
このときもらえる額は払った額より必ず少ない。
Cさんのところで紙幣、硬貨の種類を問わずちょうど$D_c$円払うと、($D_c$円より多く払うことは出来ない)
1000円札を$C_{1000}$枚、100円玉を$C_{100}$枚、1円玉を$C_{1}$枚もらえる。
このときももらえる額は払った額より必ず少ない。
BさんもしくはCさんにお金を払ってお金をもらう行為を1回のお使いとする。
A君はお使いにたくさん行くと褒められる。
A君はBさんCさんにお使いに行く順番と支払い方法を工夫してたくさんお使いに行きたい。
A君が行くことのできる最大のお使いの回数は何回か?。

入力

$A_{1000}$ $A_{100}$ $A_{1}$
$D_b$
$B_{1000}$ $B_{100}$ $B_{1}$
$D_c$
$C_{1000}$ $C_{100}$ $C_{1}$

A君の最初の所持金は最大$10000$円である。
よって、$0 \le A_{1000}\times 1000+A_{100}\times 100+A_{1} \le 10000$。$A_{1000}$,$A_{100}$,$A_{1}$はすべて$0$以上の整数。
$1 \le D_b,D_c \le 10000$。$D_b$,$D_c$は正の整数。
$B_{1000}\times 1000+B_{100}\times 100+B_{1} < D_b$。$B_{1000}$,$B_{100}$,$B_{1}$はすべて$0$以上の整数。
$C_{1000}\times 1000+C_{100}\times 100+C_{1} < D_c$。$C_{1000}$,$C_{100}$,$C_{1}$はすべて$0$以上の整数。

出力

A君が行くことのできる最多のお使いの回数を1行で答えよ。
答えの最後には改行を忘れずに。

サンプル

サンプル1
入力
0 1 12
110
0 1 2
6
0 0 1
出力
2

A君は最初1000円札を0枚、100円玉を1枚、1円玉を12枚持っている。
例えば、Bさんのところに行くと110円を100円玉1枚と1円玉2枚に変えてくれる。
Bさんのところに行った後には100円玉1枚と1円玉4枚が残る。
もうこれ以上お使いに行くことはできない。
例えば、Cさんのところに行くと6円を1円玉1枚に変えてくれる。
Cさんのところには2回お使いに行くことができる。
Cさんのところに2回行った後には100円玉1枚と1円玉2枚が残る。
もうこれ以上お使いに行くことはできない。
以上のことからCさんのところに2回行くことによって最大2回のお使いができる。

サンプル2
入力
10 0 0
900
0 5 300
1001
1 0 0
出力
0

A君は最初1000円札を10枚、100円玉を0枚、1円玉を0枚持っている。
Bさんのところに行くと900円を100円玉5枚と1円玉300枚に変えてくれる。
Cさんのところに行くと1001円を1000円札1枚に変えてくれる。
しかし、A君は1000円札しか持っていないので900円も1001円もちょうど払えない。
よってお使いには1回も行くことはできない。

サンプル3
入力
0 1 0
100
0 0 12
3
0 0 1
出力
6

A君は最初1000円札を0枚、100円玉を1枚、1円玉を0枚持っている。
まず、Bさんのところに行って100円を1円玉12枚に変える。
次に、Cさんのところで3円を1円玉に変えるお使いを5回行う。
合計6回のお使いができる。

サンプル4
入力
2 30 2572
5088
3 11 403
8447
1 1 3378
出力
5

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。