Орехус застрял в плоском мире. Чтобы выбраться, необходимо решить следующую задачу.
Вам даны 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]
).
Гарантируется, что нет вложенных прямоугольников.
Выведите ответ на задачу - максимальное значение, которое можно получить.