#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
const long long int mod1 = 998244353;
void fastscan(long long int &number) {
  bool negative = false;
  register int c;
  number = 0;
  c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number *= -1;
}
bool isprime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool checkisTree(long long int degree[], long long int n) {
  long long int deg_sum = 0;
  for (long long int i = 0; i < n; i++) deg_sum += degree[i];
  return (2 * (n - 1) == deg_sum);
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int findS(long long int s) {
  int l = 1, r = (s / 2) + 1;
  while (l <= r) {
    long long int mid = (l + r) / 2;
    long long int sum = mid * (mid + 1) / 2;
    if (sum == s)
      return mid;
    else if (sum > s)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return -1;
}
int main() {
  cin.sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  cin.tie(0);
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int b, p, f, h, c, ans = 0;
    cin >> b >> p >> f >> h >> c;
    if (c > h) {
      if (b / 2 > f) {
        b -= 2 * f;
        ans += f * c;
        if (b / 2 > p)
          ans += h * p;
        else
          ans += (b / 2) * h;
      } else
        ans += (b / 2) * c;
    } else {
      if (b / 2 > p) {
        b -= 2 * p;
        ans += p * h;
        if (b / 2 > f)
          ans += f * c;
        else
          ans += (b / 2) * c;
      } else
        ans += (b / 2) * h;
    }
    cout << ans << endl;
  }
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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;
const long long int mod = 1e9 + 7;
const long long int mod1 = 998244353;
void fastscan(long long int &number) {
  bool negative = false;
  register int c;
  number = 0;
  c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number *= -1;
}
bool isprime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool checkisTree(long long int degree[], long long int n) {
  long long int deg_sum = 0;
  for (long long int i = 0; i < n; i++) deg_sum += degree[i];
  return (2 * (n - 1) == deg_sum);
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int findS(long long int s) {
  int l = 1, r = (s / 2) + 1;
  while (l <= r) {
    long long int mid = (l + r) / 2;
    long long int sum = mid * (mid + 1) / 2;
    if (sum == s)
      return mid;
    else if (sum > s)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return -1;
}
int main() {
  cin.sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  cin.tie(0);
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int b, p, f, h, c, ans = 0;
    cin >> b >> p >> f >> h >> c;
    if (c > h) {
      if (b / 2 > f) {
        b -= 2 * f;
        ans += f * c;
        if (b / 2 > p)
          ans += h * p;
        else
          ans += (b / 2) * h;
      } else
        ans += (b / 2) * c;
    } else {
      if (b / 2 > p) {
        b -= 2 * p;
        ans += p * h;
        if (b / 2 > f)
          ans += f * c;
        else
          ans += (b / 2) * c;
      } else
        ans += (b / 2) * h;
    }
    cout << ans << endl;
  }
}

```