JOI Kingdom terkenal sebagai penghasil emas. Di JOI Kingdom, sekali setiap tahun, sebuah buldoser digunakan untuk menambang emas.

Wilayah JOI Kingdom digambarkan sebagai bidang dengan koordinat $xy$. Ada $N$ titik di wilayah tersebut. Titik ke-$i$ ($1 \le i \le N$) berada di $(X_i,Y_i)$. Setiap titik mengandung emas atau batu, tetapi tidak keduanya.

Jika titik $i$ mengandung emas, ketika kita menambangnya satu kali, kita memperoleh emas dengan nilai $V_i$. Jika titik $i$ mengandung batu, ketika kita menambangnya satu kali, kita memperoleh batu. Biaya untuk membuangnya adalah $C_i$.

Kita menggunakan buldoser untuk menambang dengan cara berikut. Pertama, kita memilih dua garis sejajar pada bidang $xy$. Kemudian, kita menambang seluruh emas dan batu, masing-masing satu kali, di daerah antara kedua garis sejajar tersebut (termasuk emas atau batu yang terletak pada kedua garis).

Keuntungan JOI Kingdom adalah jumlah nilai emas di daerah penambangan dikurangi jumlah biaya pembuangan batu di daerah yang sama. Kita ingin memaksimalkan keuntungan JOI Kingdom.

Tugas

Tulislah program yang menghitung keuntungan maksimum JOI Kingdom.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama masukan berisi sebuah bilangan bulat $N$, yaitu banyaknya titik tempat kita dapat mengambil emas atau batu.

• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi tiga bilangan bulat $X_i$, $Y_i$, $W_i$ yang dipisahkan oleh spasi.

  • Jika $W_i \ge 1$, titik ke-$i$, $(X_i,Y_i)$, mengandung emas. Ketika kita menambangnya satu kali, kita memperoleh emas dengan nilai $V_i=W_i$.
  • Jika $W_i \le -1$, titik ke-$i$, $(X_i,Y_i)$, mengandung batu. Ketika kita menambangnya satu kali, kita memperoleh batu, dan biaya pembuangannya adalah $C_i=-W_i$.

  Berlaku $W_i \ne 0$.

Keluaran

Tulislah satu baris ke keluaran standar. Keluaran berisi keuntungan maksimum JOI Kingdom.

Batasan

Seluruh data masukan memenuhi ketentuan berikut.

• $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$).

Subsoal

Ada 5 subsoal. Skor dan batasan tambahan setiap subsoal adalah sebagai berikut:

Subsoal 1 [5 poin]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). Dengan kata lain, seluruh titik terletak pada sumbu $x$.

Subsoal 2 [20 poin]

• $N \le 100$.
• Tidak ada tiga titik berbeda yang terletak pada satu garis.
• Misalkan $L$ adalah garis pada bidang $xy$ yang melalui dua titik berbeda. Misalkan $L'$ adalah garis lain, berbeda dari $L$, pada bidang $xy$ yang melalui dua titik berbeda. Maka, $L$ dan $L'$ tidak sejajar.

Subsoal 3 [35 poin]

• Tidak ada tiga titik berbeda yang terletak pada satu garis.
• Misalkan $L$ adalah garis pada bidang $xy$ yang melalui dua titik berbeda. Misalkan $L'$ adalah garis lain, berbeda dari $L$, pada bidang $xy$ yang melalui dua titik berbeda. Maka, $L$ dan $L'$ tidak sejajar.

Subsoal 4 [20 poin]

• Tidak ada tiga titik berbeda yang terletak pada satu garis.

Subsoal 5 [20 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

19

Penjelasan

Pada Contoh Masukan 1, posisi emas dan batu di JOI Kingdom adalah sebagai berikut.

Pada contoh masukan ini, kita dapat mengambil emas atau batu di titik 2, 3, 4, 5. Keuntungan JOI Kingdom saat itu adalah $19$. Inilah keuntungan maksimum JOI Kingdom.

Masukan 2

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

Keluaran 2

15

Penjelasan

Pada Contoh Masukan 2, titik 1, 2, 3 terletak pada satu garis. Titik 4, 5, 6 juga terletak pada satu garis.

Masukan 3

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

Keluaran 3

5

Penjelasan

Pada Contoh Masukan 3, tidak ada tiga titik berbeda yang terletak pada satu garis. Misalkan $L$ adalah garis yang melalui titik 1 dan 2, dan $L'$ adalah garis yang melalui titik 3 dan 4. Maka, $L$ dan $L'$ sejajar.

Masukan 4

2
0 0 -1
1 0 -1

Keluaran 4

0

Penjelasan

Kita dapat memilih daerah yang tidak mengandung emas ataupun batu. Pada Contoh Masukan 4, keuntungan maksimumnya adalah $0$.

Masukan 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

Keluaran 5

107