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

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

---