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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Iterator;
import java.io.IOException;
import java.util.TreeSet;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CKalilaAndDimnaInTheLoggingIndustry solver = new CKalilaAndDimnaInTheLoggingIndustry();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CKalilaAndDimnaInTheLoggingIndustry {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int[] a = in.ri(n);
            int[] b = in.ri(n);
            LongConvexHullTrick cht = new LongConvexHullTrick();
            long[] dp = new long[n];
            dp[0] = 0;
            cht.insert(-b[0], -dp[0]);
            for (int i = 1; i < n; i++) {
                dp[i] = -cht.query(a[i]);
                cht.insert(-b[i], -dp[i]);
            }
            long ans = dp[n - 1];
            out.println(ans);
        }

    }

    static class LongConvexHullTrick implements Iterable<LongConvexHullTrick.Line> {
        static final long INF = Long.MAX_VALUE / 2;
        TreeSet<LongConvexHullTrick.Line> setSortedByA = new TreeSet<>(LongConvexHullTrick.Line.sortByA);
        TreeSet<LongConvexHullTrick.Line> setSortedByL = new TreeSet<>(LongConvexHullTrick.Line.sortByL);
        private LongConvexHullTrick.Line qBody = new LongConvexHullTrick.Line(0, 0);

        private long intersect(LongConvexHullTrick.Line x, LongConvexHullTrick.Line y) {
            assert y.a > x.a;
            return DigitUtils.ceilDiv(x.b - y.b, y.a - x.a);
        }

        private void removeLine(LongConvexHullTrick.Line line) {
            setSortedByA.remove(line);
            setSortedByL.remove(line);
        }

        private void addLine(LongConvexHullTrick.Line line) {
            setSortedByA.add(line);
            setSortedByL.add(line);
        }

        public LongConvexHullTrick.Line queryLine(long x) {
            qBody.l = x;
            return setSortedByL.floor(qBody);
        }

        public long query(long x) {
            return queryLine(x).y(x);
        }

        public LongConvexHullTrick.Line insert(long a, long b) {
            LongConvexHullTrick.Line line = new LongConvexHullTrick.Line(a, b);

            while (true) {
                LongConvexHullTrick.Line floor = setSortedByA.floor(line);
                if (floor == null) {
                    line.l = -INF;
                    break;
                }
                if (floor.a == line.a) {
                    if (floor.b >= line.b) {
                        return line;
                    } else {
                        removeLine(floor);
                        continue;
                    }
                }

                long r = intersect(floor, line);
                if (r <= floor.l) {
                    removeLine(floor);
                    continue;
                }

                floor.r = Math.min(floor.r, r);
                line.l = r;
                break;
            }

            while (true) {
                LongConvexHullTrick.Line ceil = setSortedByA.ceiling(line);
                if (ceil == null) {
                    line.r = INF;
                    break;
                }
                long r = intersect(line, ceil);
                if (r >= ceil.r) {
                    removeLine(ceil);
                    continue;
                }
                ceil.l = Math.max(ceil.l, r);
                line.r = r;
                break;
            }

            if (!line.isEmpty()) {
                addLine(line);
            }
            return line;
        }

        public Iterator<LongConvexHullTrick.Line> iterator() {
            return setSortedByA.iterator();
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (LongConvexHullTrick.Line line : this) {
                builder.append(line).append('\n');
            }
            return builder.toString();
        }

        public static class Line {
            public long a;
            public long b;
            public long l;
            public long r;
            static Comparator<LongConvexHullTrick.Line> sortByA = (x, y) -> Long.compare(x.a, y.a);
            static Comparator<LongConvexHullTrick.Line> sortByL = (x, y) -> Long.compare(x.l, y.l);

            public Line(long a, long b) {
                this.a = a;
                this.b = b;
            }

            public long y(long x) {
                return a * x + b;
            }

            public boolean isEmpty() {
                return r <= l;
            }

            public String toString() {
                return String.format("%dx+%d", a, b);
            }

        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long floorDiv(long a, long b) {
            return a < 0 ? -ceilDiv(-a, b) : a / b;
        }

        public static long ceilDiv(long a, long b) {
            if (a < 0) {
                return -floorDiv(-a, b);
            }
            long c = a / b;
            if (c * b < a) {
                return c + 1;
            }
            return c;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int[] ri(int n) {
            int[] ans = new int[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            boolean rev = false;

            skipBlank();
            if (next == '+' || next == '-') {
                rev = next == '-';
                next = read();
            }

            int val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 - next + '0';
                next = read();
            }

            return rev ? val : -val;
        }

    }
}

