Vương quốc JOI nổi tiếng về sản xuất vàng. Ở Vương quốc JOI, mỗi năm một lần, người ta dùng máy ủi để khai thác vàng.
Đất đai của Vương quốc JOI được mô tả bằng một mặt phẳng tọa độ $xy$. Có $N$ điểm trên vùng đất này. Điểm thứ $i$ ($1 \le i \le N$) là $(X_i,Y_i)$. Mỗi điểm chứa vàng hoặc đá, nhưng không chứa cả hai.
Nếu điểm $i$ chứa vàng, khi khai thác một lần, ta thu được vàng có giá trị $V_i$. Nếu điểm $i$ chứa đá, khi khai thác một lần, ta thu được đá. Chi phí để loại bỏ lượng đá đó là $C_i$.
Ta dùng máy ủi để khai thác theo cách sau. Đầu tiên, chọn hai đường thẳng song song trên mặt phẳng $xy$. Sau đó, khai thác toàn bộ vàng và đá trong vùng giữa hai đường thẳng, mỗi điểm một lần (bao gồm cả vàng hoặc đá nằm trên hai đường thẳng).
Lợi nhuận của Vương quốc JOI bằng tổng giá trị vàng trong vùng khai thác trừ đi tổng chi phí loại bỏ đá trong cùng vùng đó. Ta muốn tối đa hóa lợi nhuận của Vương quốc JOI.
Yêu cầu
Hãy viết chương trình tính lợi nhuận lớn nhất của Vương quốc JOI.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Dòng đầu tiên chứa một số nguyên $N$, là số điểm có thể lấy vàng hoặc đá.
Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa ba số nguyên $X_i,Y_i,W_i$ cách nhau bởi dấu cách.
- Nếu $W_i \ge 1$, điểm thứ $i$ tại $(X_i,Y_i)$ chứa vàng. Khi khai thác một lần, ta thu được vàng có giá trị $V_i=W_i$.
- Nếu $W_i \le -1$, điểm thứ $i$ tại $(X_i,Y_i)$ chứa đá. Khi khai thác một lần, ta thu được đá, và chi phí loại bỏ lượng đá đó là $C_i=-W_i$.
Điều kiện $W_i \ne 0$ được thỏa mãn.
Dữ liệu ra
Ghi một dòng ra đầu ra chuẩn. Dòng đó chứa lợi nhuận lớn nhất của Vương quốc JOI.
Giới hạn
Tất cả dữ liệu vào thỏa mãn các điều kiện sau.
- $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$).
Nhiệm vụ con
Có 5 nhiệm vụ con. Điểm số và các giới hạn bổ sung của từng nhiệm vụ con như sau:
Nhiệm vụ con 1 [5 điểm]
- $N \le 100$.
- $Y_i=0$ ($1 \le i \le N$). Nói cách khác, tất cả các điểm nằm trên trục $x$.
Nhiệm vụ con 2 [20 điểm]
- $N \le 100$.
- Không có ba điểm phân biệt nào nằm trên cùng một đường thẳng.
- Gọi $L$ là một đường thẳng trên mặt phẳng $xy$ đi qua hai điểm phân biệt. Gọi $L'$ là một đường thẳng khác $L$ trên mặt phẳng $xy$, đi qua hai điểm phân biệt. Khi đó, $L$ và $L'$ không song song với nhau.
Nhiệm vụ con 3 [35 điểm]
- Không có ba điểm phân biệt nào nằm trên cùng một đường thẳng.
- Gọi $L$ là một đường thẳng trên mặt phẳng $xy$ đi qua hai điểm phân biệt. Gọi $L'$ là một đường thẳng khác $L$ trên mặt phẳng $xy$, đi qua hai điểm phân biệt. Khi đó, $L$ và $L'$ không song song với nhau.
Nhiệm vụ con 4 [20 điểm]
- Không có ba điểm phân biệt nào nằm trên cùng một đường thẳng.
Nhiệm vụ con 5 [20 điểm]
Không có giới hạn bổ sung.
Ví dụ
Dữ liệu vào 1
5 -5 5 -2 2 5 10 1 4 -2 4 -5 4 -2 2 7
Dữ liệu ra 1
19
Ghi chú
Trong dữ liệu vào ví dụ 1, vị trí của vàng và đá ở Vương quốc JOI như sau.
Gold: vàng; Rock: đá.
Trong ví dụ này, ta có thể lấy vàng hoặc đá ở các điểm $2,3,4,5$. Khi đó, lợi nhuận của Vương quốc JOI là 19. Đây là lợi nhuận lớn nhất của Vương quốc JOI.
Dữ liệu vào 2
6 0 0 6 1 0 -2 2 0 8 0 1 -2 1 1 5 2 1 -2
Dữ liệu ra 2
15
Ghi chú
Trong dữ liệu vào ví dụ 2, các điểm $1,2,3$ nằm trên cùng một đường thẳng. Các điểm $4,5,6$ cũng nằm trên cùng một đường thẳng.
Dữ liệu vào 3
5 0 0 2 4 0 2 3 2 -1 1 2 2 1 1 -1
Dữ liệu ra 3
5
Ghi chú
Trong dữ liệu vào ví dụ 3, không có ba điểm phân biệt nào nằm trên cùng một đường thẳng. Gọi $L$ là đường thẳng đi qua các điểm $1$ và $2$, và gọi $L'$ là đường thẳng đi qua các điểm $3$ và $4$. Khi đó, $L$ và $L'$ song song với nhau.
Dữ liệu vào 4
2 0 0 -1 1 0 -1
Dữ liệu ra 4
0
Ghi chú
Có thể chọn vùng không chứa vàng hay đá. Trong dữ liệu vào ví dụ 4, lợi nhuận lớn nhất là 0.
Dữ liệu vào 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
Dữ liệu ra 5
107