Королевство JOI славится добычей золота. Раз в год в королевстве JOI используют бульдозер для добычи золота.

Земля королевства JOI представлена плоскостью с координатами $xy$. На ней есть $N$ точек. Точка $i$ ($1 \le i \le N$) имеет координаты $(X_i,Y_i)$. В каждой точке находится либо золото, либо камень, но не то и другое одновременно.

Если в точке $i$ находится золото, то при однократной разработке этой точки мы получаем золото стоимостью $V_i$. Если в точке $i$ находится камень, то при однократной разработке этой точки мы получаем камень. Стоимость его удаления равна $C_i$.

Бульдозер используется для добычи следующим образом. Сначала мы выбираем две параллельные прямые на плоскости $xy$. Затем мы добываем всё золото и все камни в области между этими прямыми, каждый объект ровно один раз (включая золото и камни, лежащие на самих прямых).

Прибыль королевства JOI равна суммарной стоимости золота в области добычи за вычетом суммарной стоимости удаления камней в той же области. Мы хотим максимизировать прибыль королевства JOI.

Задача

Напишите программу, которая вычисляет максимальную прибыль королевства JOI.

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

Прочитайте следующие данные из стандартного ввода.

• Первая строка содержит целое число $N$ — количество точек, в которых можно добыть золото или камень.

• Строка $i$ ($1 \le i \le N$) из следующих $N$ строк содержит три целых числа $X_i$, $Y_i$, $W_i$, разделённых пробелами.

  • Если $W_i \ge 1$, в точке $i$ с координатами $(X_i,Y_i)$ находится золото. При однократной разработке этой точки мы получаем золото стоимостью $V_i=W_i$.
  • Если $W_i \le -1$, в точке $i$ с координатами $(X_i,Y_i)$ находится камень. При однократной разработке этой точки мы получаем камень, и стоимость его удаления равна $C_i=-W_i$.

  Выполняется $W_i \ne 0$.

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

Выведите одну строку в стандартный вывод. Она должна содержать максимальную прибыль королевства JOI.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $1 \le N \le 2\,000$.
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le |W_i| \le 1\,000\,000\,000$.
• $(X_i,Y_i) \ne (X_j,Y_j)$ ($1 \le i < j \le N$).

Подзадачи

Есть 5 подзадач. Баллы и дополнительные ограничения для каждой из них приведены ниже.

Подзадача 1 [5 баллов]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). Иными словами, все точки лежат на оси $x$.

Подзадача 2 [20 баллов]

• $N \le 100$.
• Никакие три различные точки не лежат на одной прямой.
• Пусть $L$ — прямая на плоскости $xy$, проходящая через две различные точки. Пусть $L'$ — другая прямая на плоскости $xy$, отличная от $L$ и проходящая через две различные точки. Тогда $L$ и $L'$ не параллельны.

Подзадача 3 [35 баллов]

• Никакие три различные точки не лежат на одной прямой.
• Пусть $L$ — прямая на плоскости $xy$, проходящая через две различные точки. Пусть $L'$ — другая прямая на плоскости $xy$, отличная от $L$ и проходящая через две различные точки. Тогда $L$ и $L'$ не параллельны.

Подзадача 4 [20 баллов]

• Никакие три различные точки не лежат на одной прямой.

Подзадача 5 [20 баллов]

Дополнительных ограничений нет.

Примеры

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

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

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

19

Примечание

В первом примере золото и камни в королевстве JOI расположены следующим образом.

В этом примере можно добыть золото или камни в точках $2,3,4,5$. Тогда прибыль королевства JOI равна $19$. Это максимальная прибыль королевства JOI.

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

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

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

15

Примечание

Во втором примере точки $1,2,3$ лежат на одной прямой. Точки $4,5,6$ также лежат на одной прямой.

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

5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1

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

5

Примечание

В третьем примере никакие три различные точки не лежат на одной прямой. Пусть $L$ — прямая, проходящая через точки $1$ и $2$, а $L'$ — прямая, проходящая через точки $3$ и $4$. Тогда $L$ и $L'$ параллельны.

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

2
0 0 -1
1 0 -1

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

0

Примечание

Можно выбрать область, в которой нет ни золота, ни камней. В четвёртом примере максимальная прибыль равна $0$.

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

15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13

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

107