Problem: ICPC World Finals Day 2

Mr. Tee and his colleagues arrived at the airport terminal. From now on, I will transfer the plane and board the enemy land R country. Since we go through Country D, we have to exchange our money into two currencies.

Mr. Kay "How does Mr. Tee exchange money?"

Mr. Tee "Huff Huff Huff Huff Huff Huff Huff Huff"

Mr. Kay "I see. I will allocate 20,000 yen for country D and 5,000 yen for country R."

Mr. Tee "Huff Huff Huff Huff Huff Huff Huff Huff"

Mr. Kay "That's strange. The exchange result is different from mine ..."

problem

One traveler is thinking of leaving Japan, sightseeing in country D (currency unit D) and country R (currency unit R), and returning to Japan. I have a \\ (M \\) yen now. I know that \\ (c_ {D} \\) [D] and \\ (c_ {R} \\) [R] will be consumed in each country, so I want to exchange money so that I don't run out of money. \\ (x \\) If you exchange yen for D country money, \\ (\ lfloa \ frac {r_ {D} x} {100} \ rfloor \\) [D], \\ (x \\) If you exchange yen for R country money, it becomes \\ (\ lfloa \ frac {r_ {R} x} {100} \ rfloor \\) [R].

For example, if you exchange 150 yen for D country money at \\ (r_ {D} = 11, c_ {D} = 10 \\), \\ (\ lfloor \ frac {11 \ times 150} {100} \ rfloor = \\) 16 [D] so there is no shortage of money. However, if you exchange only 50 yen, it will be 5 [D] and less than 10 [D], so you will run out of money.

Also, when returning to Japan, all the money on hand will be exchanged for Japanese yen. If you exchange \\ (x \\) [D] for Japanese Yen, you will get \\ (\ lfloor \ frac {100x} {r_ {D}} \ rfloor \\) Yen, \\ (x \\) [R] Is converted into Japanese Yen, which becomes \\ (\ lfloor \ frac {100x} {r_ {R}} \ rfloor \\) Yen.

In the first example above, 10 [D] of the obtained 16 [D] are consumed, so 6 [D] is left over. If you exchange this for Japanese Yen, it will be \\ (\ lfloor \ frac {100 \ times 6} {11} \ rfloor = 54 \\) Yen.

Find the maximum amount of Japanese Yen that will eventually be returned to you when you return to Japan when you have optimally exchanged Japanese Yen at the time of departure. No matter what kind of exchange you make, if you run out of money in either Country D or Country R, ​​output "-1".

* \\ (\ lfloor x \ rfloor \\) represents the largest integer that does not exceed \\ (x \\).

input


M rD rR cD cR


The first line is the amount of Japanese Yen you currently have \\ (M \\), the exchange rate between Japanese Yen and the currency unit of Country D \\ (r_ {D} \\), the currency unit of Japanese Yen and Country R Exchange rate with \\ (r_ {R} \\), money consumption in country D \\ (c_ {D} \\), money consumption in country R \\ (c_ {R} \ \) Is given separated by spaces.

output

Output the maximum amount of Japanese Yen that will be returned to you on one line. No matter what kind of exchange you make, if you run out of money in either Country D or Country R, ​​output "-1".

Constraint

* \\ (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) \\)


Input / output example

Input 1


20000 3 1 20 100


Output 1


9333


If you convert 667 yen to country D money and 10,000 yen to country R money, you will get 20 [D] and 100 [R], respectively.

Input 2


1000000000000 3 1 20 100


Output 2


999999989333


This traveler is very rich.

Input 3


0 3 1 20 100


Output 3


-1


This traveler is sentenceless and can't go anywhere.





Example

Input

M r


Output

9333

Solution (in CPP):

Solution:
#include <iostream>
using namespace std;

long long search(long long r, long long c) {
	long long low = -1, high = 100ll * c;
	while(high - low > 1) {
		const long long mid = (low + high) / 2;
		if(r * mid / 100ll >= c) {
			high = mid;
		}
		else {
			low = mid;
		}
	}

	return high;
}

inline long long f(long long x, long long r, long long c) {
	return (r * x / 100 - c) * 100 / r;
}

int main() {
	long long M, rD, rR, cD, cR;
	cin >> M >> rD >> rR >> cD >> cR;

	long long minXD = search(rD, cD);
	long long minXR = search(rR, cR);

	long long ans = -1;

	if(minXD + minXR <= M) {
		for(int i = 0; i < 100; ++i) {
			for(int j = 0; j < 100; ++j) {
				const long long payD = minXD + i;
				const long long payR = minXR + j;
				const long long rest = M - payD - payR;
				if(rest < 0)
					continue;

				ans = max(ans, rest + f(payD, rD, cD) + f(payR, rR, cR));
			}
		}
	}

	cout << ans << endl;

	return 0;
}