تشتهر JOI Kingdom بإنتاج الذهب. ويستخدم أهل JOI Kingdom جرافة لاستخراج الذهب مرة كل عام.

تُمثَّل أرض JOI Kingdom بمستوى ذي إحداثيات $xy$. وتوجد $N$ نقطة في الأرض. النقطة رقم $i$ ($1 \le i \le N$) هي $(X_i,Y_i)$. تحتوي كل نقطة إما على ذهب وإما على صخر، ولا تحتوي عليهما معًا.

إذا احتوت النقطة $i$ على ذهب، نحصل عند تعدينها مرة واحدة على ذهب قيمته $V_i$. وإذا احتوت النقطة $i$ على صخر، نحصل عند تعدينها مرة واحدة على صخر، وتكلفة التخلص منه هي $C_i$.

نستخدم الجرافة في التعدين بالطريقة التالية. أولًا، نختار خطين مستقيمين متوازيين في المستوى $xy$. ثم نُعدِّن كل الذهب والصخر في المنطقة الواقعة بين الخطين المتوازيين، مرة واحدة لكل منهما (بما في ذلك الذهب أو الصخر الواقع على الخطين).

ربح JOI Kingdom هو القيمة الإجمالية للذهب في منطقة التعدين ناقص التكلفة الإجمالية للتخلص من الصخر في المنطقة نفسها. ونريد تعظيم ربح JOI Kingdom.

المهمة

اكتب برنامجًا يحسب أكبر ربح ممكن لـJOI Kingdom.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول من الإدخال على عدد صحيح $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 Kingdom.

القيود

تحقق جميع بيانات الإدخال الشروط التالية.

• $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 Kingdom كما يلي.

الذهب (Gold)، الصخر (Rock).

في هذا المثال من الإدخال، يمكننا أخذ الذهب أو الصخر من النقاط $2,3,4,5$. عندئذ، يكون ربح JOI Kingdom هو $19$. وهذا هو أكبر ربح ممكن لـJOI Kingdom.

الإدخال 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