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.
#include <bits/stdc++.h>
using namespace std;
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
inline void readWord(char *s) {
  int c = readChar();
  while (c > 32) *s++ = c, c = getChar();
  *s = 0;
}
inline void writeDouble(double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = min(9, (int)(x + 0.5));
  writeChar('0' + t);
}
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using ull = unsigned long long;
using pnt = complex<ld>;
istream &operator>>(istream &in, pnt &p) {
  ld a, b;
  in >> a >> b;
  p = {a, b};
  return in;
}
ld crs(pnt a, pnt b) { return a.real() * b.imag() - a.imag() * b.real(); }
ld dot(pnt a, pnt b) { return a.real() * b.real() + a.imag() * b.imag(); }
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 1e18L;
const ld pi = acos(-1.0L);
const ld eps = 1e-9L;
const int di[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dj[] = {2, -2, 2, -2, 1, -1, 1, -1};
const int dii[] = {0, 1, -1, 0};
const int djj[] = {1, 0, 0, -1};
const int dx[] = {1, 1, -1, -1};
const int dy[] = {1, -1, 1, -1};
const int SQ = 1000;
const int LG = 19;
const int nax = 1e6 + 10;
struct Line {
  ll k, b;
  int cnt;
  ll eval(ld x) { return k * x + b; }
};
inline ld isec(Line &p, Line &q) { return ((ld)p.b - q.b) / (q.k - p.k); }
struct CHT {
  int s;
  Line l[nax];
  void clr() { s = 0; }
  void add(Line a) {
    while (s >= 2 && isec(l[s - 2], l[s - 1]) >= isec(l[s - 1], a)) s--;
    l[s++] = a;
  }
  ll get(ll x) {
    int lf = 1, rg = s - 1;
    if (s == 1 || x <= isec(l[0], l[1]))
      lf = 0;
    else
      while (lf < rg) {
        int md = (lf + rg + 1) >> 1;
        if (isec(l[md - 1], l[md]) <= x)
          lf = md;
        else
          rg = md - 1;
      }
    return l[lf].eval(x);
  }
};
struct rect {
  ll x, y, a;
  bool operator<(const rect &he) const { return x < he.x; }
};
int n;
rect a[nax];
ll dp[nax];
CHT cht;
ll ans;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout.precision(8);
  cout << fixed;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> a[i].a;
  sort(a, a + n);
  cht.clr();
  cht.add({0, 0, 0});
  for (int i = 0; i < n; i++) {
    dp[i] = cht.get(-a[i].y) + a[i].x * a[i].y - a[i].a;
    cht.add({a[i].x, dp[i]});
    ans = max(ans, dp[i]);
  }
  cout << ans;
}
