시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB137753.846%

문제

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.

입력

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.

출력

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

예제 입력 1

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

예제 출력 1

4
14
13
16
7120
54

예제 입력 2

3
1 1 1 1 1
100000000 100000000 100000000 100000000 100000000
91965976 48437754 31825605 1671338 8268468

예제 출력 2

1
10000000000000000
2954637341500842