#include <bits/stdc++.h>
using namespace std;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  register int x = 0, f = 1;
  register char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = nc();
  return x * f;
}
inline void write(register int x) {
  if (!x) putchar('0');
  if (x < 0) x = -x, putchar('-');
  static int sta[20];
  register int tot = 0;
  while (x) sta[tot++] = x % 10, x /= 10;
  while (tot) putchar(sta[--tot] + 48);
}
int T, n, m, k, a, b, ans;
int main() {
  T = read();
  while (T--) {
    ans = 0;
    n = read(), m = read(), k = read();
    a = read(), b = read();
    if (a < b) swap(a, b), swap(m, k);
    ans += a * min(n / 2, m);
    n -= 2 * min(n / 2, m);
    ans += b * min(n / 2, k);
    write(ans), puts("");
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

There are two types of burgers in your restaurant — hamburgers and chicken burgers! To assemble a hamburger you need two buns and a beef patty. To assemble a chicken burger you need two buns and a chicken cutlet. 

You have b buns, p beef patties and f chicken cutlets in your restaurant. You can sell one hamburger for h dollars and one chicken burger for c dollars. Calculate the maximum profit you can achieve.

You have to answer t independent queries.

Input

The first line contains one integer t (1 ≤ t ≤ 100) – the number of queries.

The first line of each query contains three integers b, p and f (1 ≤ b, ~p, ~f ≤ 100) — the number of buns, beef patties and chicken cutlets in your restaurant.

The second line of each query contains two integers h and c (1 ≤ h, ~c ≤ 100) — the hamburger and chicken burger prices in your restaurant.

Output

For each query print one integer — the maximum profit you can achieve.

Example

Input


3
15 2 3
5 10
7 5 2
10 12
1 100 100
100 100


Output


40
34
0

Note

In first query you have to sell two hamburgers and three chicken burgers. Your income is 2 ⋅ 5 + 3 ⋅ 10 = 40.

In second query you have to ell one hamburgers and two chicken burgers. Your income is 1 ⋅ 10 + 2 ⋅ 12 = 34.

In third query you can not create any type of burgers because because you have only one bun. So your income is zero.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  register int x = 0, f = 1;
  register char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = nc();
  return x * f;
}
inline void write(register int x) {
  if (!x) putchar('0');
  if (x < 0) x = -x, putchar('-');
  static int sta[20];
  register int tot = 0;
  while (x) sta[tot++] = x % 10, x /= 10;
  while (tot) putchar(sta[--tot] + 48);
}
int T, n, m, k, a, b, ans;
int main() {
  T = read();
  while (T--) {
    ans = 0;
    n = read(), m = read(), k = read();
    a = read(), b = read();
    if (a < b) swap(a, b), swap(m, k);
    ans += a * min(n / 2, m);
    n -= 2 * min(n / 2, m);
    ans += b * min(n / 2, k);
    write(ans), puts("");
  }
  return 0;
}

```