Королівство 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'$ — інша пряма, відмінна від $L$, на площині $xy$, що проходить через дві різні точки. Тоді $L$ і $L'$ не паралельні одна одній.

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

• Жодні три різні точки не лежать на одній прямій.
• Нехай $L$ — пряма на площині $xy$, що проходить через дві різні точки. Нехай $L'$ — інша пряма, відмінна від $L$, на площині $xy$, що проходить через дві різні точки. Тоді $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

Пояснення

У прикладі вхідних даних 1 золото й каміння в королівстві 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

Пояснення

У прикладі вхідних даних 2 точки $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

Пояснення

У прикладі вхідних даних 3 жодні три різні точки не лежать на одній прямій. Нехай $L$ — пряма, що проходить через точки $1$ і $2$, а $L'$ — пряма, що проходить через точки $3$ і $4$. Тоді $L$ і $L'$ паралельні одна одній.

Вхідні дані 4

2
0 0 -1
1 0 -1

Вихідні дані 4

0

Пояснення

Можна вибрати область, у якій немає ані золота, ані каміння. У прикладі вхідних даних 4 максимальний прибуток становить $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