G. Get Good
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Charlie is desperate to improve his programming skills.

Starting fresh, he can work hard and gain $$$a$$$ skill points per day for $$$x$$$ consecutive days, after which he is tired. For as long as he carries on tired, he will gain $$$b$$$ skill points per day. Alternatively, he can choose at any time to take a break of $$$y$$$ consecutive days, after which he can start afresh.

There are only $$$n$$$ days available before the big contest, and Charlie starts fresh on day $$$1$$$. Help him find the maximum skill points obtainable.

Input

The first line of input contains the number of cases, $$$t$$$ ($$$1 \le t \le 10,000$$$).

Each test case consists of five integers $$$n,a,b,x,y,$$$ ($$$1 \le n \le 10^9$$$): the number of available days, ($$$10^9 \ge a \ge b \ge 1$$$) the daily skill points when fresh or tired, ($$$1 \le x, y \le 10^9$$$) the numbers of days of higher skill gain and break.

Output

For each test case, output a single integer representing the maximum skill points obtainable.

Examples
Input
6
2 2 2 2 2
4 4 2 3 3
5 3 2 3 1
5 4 1 3 1
99 80 40 30 5
10 6 1 6 1
Output
4
14
13
16
7120
54
Input
3
1 1 1 1 1
100000000 100000000 100000000 100000000 100000000
91965976 48437754 31825605 1671338 8268468
Output
1
10000000000000000
2954637341500842