ממלכת 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

הסבר

בקלט לדוגמה 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