Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money. 

The manager of logging factory wants them to go to the jungle and cut n trees with heights a1, a2, ..., an. They bought a chain saw from a shop. Each time they use the chain saw on the tree number i, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is i (the tree that have height ai in the beginning), then the cost of charging the chain saw would be bi. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each i < j, ai < aj and bi > bj and also bn = 0 and a1 = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost. 

They want you to help them! Will you?

Input

The first line of input contains an integer n (1 ≤ n ≤ 105). The second line of input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). The third line of input contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 109).

It's guaranteed that a1 = 1, bn = 0, a1 < a2 < ... < an and b1 > b2 > ... > bn.

Output

The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5
1 2 3 4 5
5 4 3 2 0


Output

25


Input

6
1 2 3 10 20 30
6 5 4 3 2 0


Output

138
#include <bits/stdc++.h>
using namespace std;
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
struct ConvexHullDynamic {
  static const long long INF = 1e18;
  struct Line {
    long long a, b;
    double xLeft;
    enum Type { line, maxQuery, minQuery } type;
    long long val;
    explicit Line(long long aa = 0, long long bb = 0)
        : a(aa), b(bb), xLeft(-INF), type(Type::line), val(0) {}
    long long valueAt(long long x) const { return a * x + b; }
    friend bool isParallel(const Line &l1, const Line &l2) {
      return l1.a == l2.a;
    }
    friend double llersectX(const Line &l1, const Line &l2) {
      return isParallel(l1, l2) ? INF : 1.0 * (l2.b - l1.b) / (l1.a - l2.a);
    }
    bool operator<(const Line &l2) const {
      if (l2.type == line) return this->a < l2.a;
      if (l2.type == maxQuery) return this->xLeft < l2.val;
      if (l2.type == minQuery) return this->xLeft > l2.val;
      return false;
    }
  };
  bool isMax;
  set<Line> hull;
  bool hasPrev(set<Line>::iterator it) { return it != hull.begin(); }
  bool hasNext(set<Line>::iterator it) {
    return it != hull.end() && next(it) != hull.end();
  }
  bool irrelevant(const Line &l1, const Line &l2, const Line &l3) {
    return llersectX(l1, l3) <= llersectX(l1, l2);
  }
  bool irrelevant(set<Line>::iterator it) {
    return hasPrev(it) && hasNext(it) &&
           ((isMax && irrelevant(*prev(it), *it, *next(it))) ||
            (!isMax && irrelevant(*next(it), *it, *prev(it))));
  }
  set<Line>::iterator updateLeftBorder(set<Line>::iterator it) {
    if (isMax && !hasPrev(it) || !isMax && !hasNext(it)) return it;
    double val = llersectX(*it, isMax ? (*prev(it)) : (*next(it)));
    Line temp(*it);
    it = hull.erase(it);
    temp.xLeft = val;
    it = hull.insert(it, temp);
    return it;
  }
  explicit ConvexHullDynamic(bool isMax) : isMax(isMax) {}
  void addLine(long long a, long long b) {
    Line l3 = Line(a, b);
    auto it = hull.lower_bound(l3);
    if (it != hull.end() && isParallel(*it, l3)) {
      if (isMax && it->b < b || !isMax && it->b > b)
        it = hull.erase(it);
      else
        return;
    }
    it = hull.insert(it, l3);
    if (irrelevant(it)) {
      hull.erase(it);
      return;
    }
    while (hasPrev(it) && irrelevant(prev(it))) hull.erase(prev(it));
    while (hasNext(it) && irrelevant(next(it))) hull.erase(next(it));
    it = updateLeftBorder(it);
    if (hasPrev(it)) updateLeftBorder(prev(it));
    if (hasNext(it)) updateLeftBorder(next(it));
  }
  long long getBest(long long x) {
    Line q;
    q.val = x;
    q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery;
    auto bestLine = hull.lower_bound(q);
    if (isMax) --bestLine;
    return bestLine->valueAt(x);
  }
};
signed main() {
  ConvexHullDynamic ds(0);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long arr[n];
  long long brr[n];
  long long i;
  for (i = 0; i < n; i++) cin >> arr[i];
  for (i = 0; i < n; i++) cin >> brr[i];
  ds.addLine(brr[0], 0);
  long long ans = 1;
  for (i = 1; i < n; i++) {
    ans = ds.getBest(arr[i]);
    ds.addLine(brr[i], ans);
  }
  cout << ans;
}
