Problem D: Change

ICPC World Finals 2日目

ティー氏らは空港のターミナルについた。 これから飛行機を乗り継ぎ敵地R国に乗り込むのである。 我々はD国を経由するため、手持ちのお金を2種類の通貨に両替せねばならない。

ケー氏「ティーさんはどのように両替しますか？」

ティー氏「ハフハフハフハフハフハフハフハフ」

ケー氏「なるほど。私も20,000円をD国用に5,000円、R国用に15,000円割り振ろうと思います」

ティー氏「ハフハフハフハフハフハフハフハフ」

ケー氏「あれ？変ですね。両替結果が私と違いますね…。」

問題

ある旅行者は、日本を旅立ち、D国（通貨単位D）、R国（通貨単位R）を観光し、日本に帰ってくることを考えている。 今、$M$円持っている。 $c_{D}$[D]、$c_{R}$[R]を各国で消費することが分かっているので、 お金が不足しないように両替したい。 $x$円をD国のお金に両替すると$\lfloor \frac{r_{D}x}{100} \rfloor$[D]に、 $x$円をR国のお金に両替すると$\lfloor \frac{r_{R}x}{100} \rfloor$[R]になる。

例えば、 $r_{D}=11, c_{D}=10$の時に 150円をD国のお金に両替すると$\lfloor \frac{11 \times 150}{100} \rfloor =$16[D]になるためお金は不足しない。 しかし、50円しか両替しないと5[D]になり10[D]に満たないためお金が不足する。

また、帰国時には手持ちのお金を全て日本円に両替する。 $x$[D]を日本円に両替すると$\lfloor \frac{100x}{r_{D}} \rfloor$円に、 $x$[R]を日本円に両替すると$\lfloor \frac{100x}{r_{R}} \rfloor$円になる。

先の1つ目の例では、 得られた16[D]のうち10[D]を消費するため6[D]余る。 これを日本円に両替すると$\lfloor \frac{100 \times 6}{11} \rfloor = 54$円になる。

出国時に日本円の最適な両替を行った時、帰国時に最終的に手元に戻ってくる日本円の最大額を求めよ。 いかなる両替を行なっても、D国またはR国のいずれかでお金が不足する場合には"-1"と出力せよ。

※$\lfloor x \rfloor$は、$x$を超えない最大の整数を表す。

入力

M rD rR cD cR

1行目に 現在手持ちの日本円の額$M$、 日本円とD国の通貨単位との両替レート$r_{D}$、 日本円とR国の通貨単位との両替レート$r_{R}$、 D国でのお金の消費額$c_{D}$、 R国でのお金の消費額$c_{R}$が空白区切りで与えられる。

出力

手元に戻ってくる日本円の最大額を1行に出力せよ。 いかなる両替を行なっても、D国またはR国のいずれかでお金が不足する場合は"-1"を出力せよ。

制約

• $0 \leq M \leq 10^{12}(= 1000000000000)$
• $1 \leq r_{D}, r_{R} \leq 100$
• $0 \leq c_{D}, c_{R} \leq 10^{12}(= 1000000000000)$

入出力例

入力1

20000 3 1 20 100

出力1

9333

667円をD国のお金に、10,000円をR国のお金に変換すれば、それぞれ20[D]、100[R]が得られる。

入力2

1000000000000 3 1 20 100

出力2

999999989333

この旅行者は大金持ちである。

入力3

0 3 1 20 100

出力3

-1

この旅行者は一文無しであり、どこにも行けない。