Горіхус і прямокутники
Орехус застряг у двовимірному світі. Щоб вибратися, йому потрібно розв'язати наступну задачу.
Вам дано n прямокутників, кожен з яких має вершини в точках (0, 0), (x[i], 0), (x[i], y[i]), (0, y[i]). Для кожного прямокутника також задано число a[i]. Потрібно вибрати деякі з цих прямокутників так, щоб різниця між площею їх об'єднання та сумою їх a[i] була максимальною.
Гарантовано, що жоден з прямокутників не є вкладеним в інший.
Орехус не знає, як розв'язати цю задачу, тому він звернувся до вас за допомогою.
Вхідні дані
У першому рядку подано одне ціле число n (1 ≤ n ≤ 10^6) — кількість прямокутників. Кожен з наступних n рядків містить три цілі числа x[i], y[i] та a[i] (1 ≤ x[i], y[i] ≤ 10^9, 0 ≤ a[i] ≤ x[i] * y[i]).
Гарантовано, що жоден з прямокутників не є вкладеним в інший.
Вихідні дані
Виведіть максимальне значення, яке можна отримати.