อาณาจักร 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