E. Орехус и прямоугольники
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Орехус застрял в плоском мире. Чтобы выбраться, необходимо решить следующую задачу.

Вам даны $$$n$$$ прямоугольников с вершинами в точках $$$(0, 0)$$$, $$$(x_i, 0)$$$, $$$(x_i, y_i)$$$, $$$(0, y_i)$$$. Также для каждого прямоугольника вам дано число $$$a_i$$$. Необходимо выбрать некоторые из них, чтобы площадь их объединения минус сумма их $$$a_i$$$ была максимальна.

Гарантируется, что нет вложенных прямоугольников.

Орехус не имеет ни малейшего понятия, как решать данную ему задачу, поэтому он обратился к вам за помощью.

Входные данные

В первой строке дано одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — число прямоугольников.

Каждая из следующих $$$n$$$ строк содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$a_i$$$ ($$$1 \leq x_i, y_i \leq 10^9$$$, $$$0 \leq a_i \leq x_i \cdot y_i$$$).

Гарантируется, что нет вложенных прямоугольников.

Выходные данные

В единственной строке выведите ответ на задачу — максимальное значение, которое можно получить.

Примеры
Входные данные
3
4 4 8
1 5 0
5 2 10
Выходные данные
9
Входные данные
4
6 2 4
1 6 2
2 4 3
5 3 8
Выходные данные
10
Примечание

В первом примере правильный ответ можно достигнуть, выбрав первый и второй прямоугольники.

Во втором примере правильный ответ можно тоже достигнуть, выбрав первый и второй прямоугольники.