The Fair Nut got stacked in planar world. He should solve this task to get out.

You are given n rectangles with vertexes in (0, 0), (x_i, 0), (x_i, y_i), (0, y_i). For each rectangle, you are also given a number a_i. Choose some of them that the area of union minus sum of a_i of the chosen ones is maximum.

It is guaranteed that there are no nested rectangles.

Nut has no idea how to find the answer, so he asked for your help.

Input

The first line contains one integer n (1 ≤ n ≤ 10^6) — the number of rectangles.

Each of the next n lines contains three integers x_i, y_i and a_i (1 ≤ x_i, y_i ≤ 10^9, 0 ≤ a_i ≤ x_i ⋅ y_i).

It is guaranteed that there are no nested rectangles.

Output

In a single line print the answer to the problem — the maximum value which you can achieve.

Examples

Input


3
4 4 8
1 5 0
5 2 10


Output


9

Input


4
6 2 4
1 6 2
2 4 3
5 3 8


Output


10

Note

In the first example, the right answer can be achieved by choosing the first and the second rectangles.

In the second example, the right answer can also be achieved by choosing the first and the second rectangles.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cunbidun
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ETheFairNutAndRectangles solver = new ETheFairNutAndRectangles();
        solver.solve(1, in, out);
        out.close();
    }

    static class ETheFairNutAndRectangles {
        private InputReader in;
        private PrintWriter out;
        private PrinterUtils printer;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
            this.printer = new PrinterUtils(out);
            int n = in.nextInt();
            Triple<Integer, Integer, Long>[] a = new Triple[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = new Triple<>(in.nextInt(), in.nextInt(), in.nextLong());
            }
            Arrays.sort(a, 1, n + 1);
            ConvexHullOptimizationMax ch = new ConvexHullOptimizationMax(n, false, false);
            ch.add(0, 0);
            long ans = 0;

            for (int i = 1; i <= n; i++) {
                long f = (long) a[i].first * (long) a[i].second - a[i].third + ch.get(a[i].second);
                ch.add(-a[i].first, f);
                ans = MaxMin.Max(f, ans);
            }
            out.println(ans);
        }

    }

    static class PrinterUtils {
        private PrintWriter out;

        public PrinterUtils(PrintWriter out) {
            this.out = out;
        }

    }

    static class ConvexHullOptimizationMax {
        private long[] A;
        private long[] B;
        private boolean increasingSlope;
        private boolean needTenary;
        private int curIt;
        private int size;

        private boolean bad(int l1, int l2, long x, long y) {
            if (increasingSlope)
                return Double.compare((double) (y - B[l2]) / (A[l2] - x), (double) (B[l2] - B[l1]) / (A[l1] - A[l2])) <= 0;
            return Double.compare((double) (y - B[l2]) / (A[l2] - x), (double) (B[l2] - B[l1]) / (A[l1] - A[l2])) >= 0;
        }

        public ConvexHullOptimizationMax(int maxSize, boolean increasingSlope, boolean needTenary) {
            this.increasingSlope = increasingSlope;
            this.needTenary = needTenary;
            A = new long[maxSize + 10];
            B = new long[maxSize + 10];
            curIt = 0;
            size = 0;
        }

        public void add(long x, long y) {
            if (size > 0 && A[size - 1] == x) {
                if (B[size - 1] >= y) return;
                while (A[size - 1] == x && B[size - 1] <= y) size--;
            }

            // change to ">=" if you want to find min
            while (size >= 2 && bad(size - 2, size - 1, x, y)) size--;
            A[size] = x;
            B[size] = y;
            size++;
            curIt = MaxMin.Min(curIt, size - 1);
        }

        public long get(long x) {
            if (!needTenary) {
                curIt = MaxMin.Min(curIt, size - 1);
                while (curIt < size - 1 && A[curIt] * x + B[curIt] <= A[curIt + 1] * x + B[curIt + 1])
                    curIt++;
                // change to ">=" if you want to find min
                return A[curIt] * x + B[curIt];
            }
            int l = 0, r = size;
            while (r - l > 2) {
                int mid1 = (l * 2 + r) / 3;
                int mid2 = (l + 2 * r) / 3;
                long val1 = A[mid1] * x + B[mid1];
                long val2 = A[mid2] * x + B[mid2];
                if (val1 == val2) {
                    l = mid1;
                    r = mid2;
                } else if (val1 < val2) l = mid1; // change to ">" if you want to find min
                else r = mid2;
            }
            long ret = (long) -1e18;
            for (int i = l; i <= r; i++)
                ret = MaxMin.Max(ret, A[i] * x + B[i]);
            return ret;
        }

    }

    static class InputReader extends InputStream {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class MaxMin {
        public static <T extends Comparable<T>> T Max(T x, T y) {
            T max = x;
            if (y.compareTo(max) > 0) max = y;
            return max;
        }

        public static <T extends Comparable<T>> T Min(T x, T y) {
            T min = x;
            if (y.compareTo(min) < 0) min = y;
            return min;
        }

    }

    static class Triple<U extends Comparable<U>, V extends Comparable<V>, W extends Comparable<W>> implements Comparable<Triple<U, V, W>> {
        public U first;
        public V second;
        public W third;

        public Triple(U first, V second, W third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }

        public String toString() {
            return "(" + first + "," + second + "," + third + ")";
        }

        public int compareTo(Triple<U, V, W> o) {
            if (first.compareTo(o.first) != 0) return first.compareTo(o.first);
            if (second.compareTo(o.second) != 0) return second.compareTo(o.second);
            else return third.compareTo(o.third);
        }

    }
}

